供应链中生产和运输协调调度问题初探

提出了解决供应链中生产和航空运输协调调度问题的理论框架.基于对生产调度和航空运输调度彼此制约关系的分析,协调调度问题被分解为两个子调度问题.建立了航空运输子调度问题的整数规划模型,并证明了该问题为NP完全问题.提出了基于倒排调度方法(backward scheduling method)的调度算法解单机生产调度子问题.     

An integrated system solution for supply chain optimization in the chemical process industry

This paper considers a complex scheduling problem in the chemical process industry involving batch production. The application described comprises a network of production plants with interdependent production schedules, multi-stage production at multi-purpose facilities, and chain production. The paper addresses three distinct aspects: (i) a scheduling solution obtained from a genetic algorithm based optimizer, (ii) a mechanism for collaborative planning among the involved plants, and (iii) a tool for manual updates and schedule changes. The tailor made optimization algorithm simultaneously considers alternative production paths and facility selection as well as product and resource specific parameters such as batch sizes, and setup and cleanup times. The collaborative planning concept allows all the plants to work simultaneously as partners in a supply chain resulting in higher transparency, greater flexibility, and reduced response time as a whole. The user interface supports monitoring production schedules graphically and provides custom-built utilities for manual changes to the production schedule, investigation of various what-if scenarios, and marketing queries. RID="*" ID="*" The authors would like to thank Hans-Otto Günther and Roland Heilmann for helpful comments on draft versions of this paper.     

β-Robust scheduling for single-machine systems with uncertain processing times

In scheduling environments with processing time uncertainty, system performance is determined by both the sequence in which jobs are ordered and the actual processing times of jobs. For these situations, the risk of achieving substandard system performance can be an important measure of scheduling effectiveness. To hedge this risk requires an explicit consideration of both the mean and the variance of system performance associated with alternative schedules, and motivates a β-robustness objective to capture the likelihood that a schedule yields actual performance no worse than a given target level. In this paper we focus on β-robust scheduling issues in single-stage production environments with uncertain processing times. We define a general β-robust scheduling objective, formulate the β-robust scheduling problem that results when job processing times are independent random variables and the performance measure of interest is the total flow time across all jobs, establish problem complexity, and develop exact and heuristic solution approaches. We then extend the 0-robust scheduling model to consider situations where the uncertainty associated with individual job processing times can be selectively controlled through resource allocation. Computational results are reported to demonstrate the efficiency and effectiveness of the solution procedures.     

Stochastic production phase design for an open pit mining complex with multiple processing streams

In a mining complex, the mine is a source of supply of valuable material (ore) to a number of processes that convert the raw ore to a saleable product or a metal concentrate for production of the refined metal. In this context, expected variation in metal content throughout the extent of the orebody defines the inherent uncertainty in the supply of ore, which impacts the subsequent ore and metal production targets. Traditional optimization methods for designing production phases and ultimate pit limit of an open pit mine not only ignore the uncertainty in metal content, but, in addition, commonly assume that the mine delivers ore to a single processing facility. A stochastic network flow approach is proposed that jointly integrates uncertainty in supply of ore and multiple ore destinations into the development of production phase design and ultimate pit limit. An application at a copper mine demonstrates the intricacies of the new approach. The case study shows a 14% higher discounted cash flow when compared to the traditional approach.     

Robust scheduling of a two-machine flow shop with uncertain processing times

This paper focuses on manufacturing environments where job processing times are uncertain. In these settings, scheduling decision makers are exposed to the risk that an optimal schedule with respect to a deterministic or stochastic model will perform poorly when evaluated relative to actual processing times. Since the quality of scheduling decisions is frequently judged as if processing times were known a priori, robust scheduling, i.e., determining a schedule whose performance (compared to the associated optimal schedule) is relatively insensitive to the potential realizations of job processing times, provides a reasonable mechanism for hedging against the prevailing processing time uncertainty. In this paper we focus on a two-machine flow shop environment in which the processing times of jobs are uncertain and the performance measure of interest is system makespan. We present a measure of schedule robustness that explicitly considers the risk of poor system performance over all potential realizations of job processing times. We discuss two alternative frameworks for structuring processing time uncertainty. For each case, we define the robust scheduling problem, establish problem complexity, discuss properties of robust schedules, and develop exact and heuristic solution approaches. Computational results indicate that robust schedules provide effective hedges against processing time uncertainty while maintaining excellent expected makespan performance     

Comparing deterministic,robust and online scheduling using entropy

We conjecture that when the uncertainty of scheduling information increases, one should change from deterministic, through robust to, finally, online scheduling techniques. Previously, extensive mathematical investigations have been carried out on the stability of a deterministic schedule for uncertain operation processing times. In this paper, we will use an empirical approach and an entropy measure to justify the transition between deterministic, robust and online scheduling. The use of an entropy measure in our context can be perceived, in a broader sense, as a pro-active approach to deal with changes in the level of information uncertainty and relative importance of each term in the total schedule execution cost. The level of information uncertainty may change due to the performance deterioration of processors (machines or human) and the replacement of old machines with new ones; and the changes in relative importance of cost elements may be due to changes in shop floor priorities and pressure from partners in the supply chain network. One can decide upon the scheduling strategies to be employed based on the latest entropy value of the information considered and the relative importance of each cost term.     

A Constraint Programming model for food processing industry: a case for an ice cream processing facility

This paper presents a Constraint Programming (CP) scheduling model for an ice cream processing facility. CP is a mathematical optimisation tool for solving problems either for optimality (for small-size problems) or good quality solutions (for large-size problems). For practical scheduling problems, a single CP solution model can be used to optimise daily production or production horizon extending for months. The proposed model minimises a makespan objective and consists of various processing interval and sequence variables and a number of production constraints for a case from a food processing industry. Its performance was compared to a Mixed Integer Linear Programming (MILP) model from the literature for optimality, speed, and competence using the partial capacity of the production facility of the case study. Furthermore, the model was tested using different product demand sizes for the full capacity of the facility. The results demonstrate both the effectiveness, flexibility, and speed of the CP models, especially for large-scale models. As an alternative to MILP, CP models can provide a reasonable balance between optimality and computation speed for large problems.     

Robust makespan minimisation in identical parallel machine scheduling problem with interval data

Parallel machine scheduling problems are commonly encountered in a wide variety of manufacturing environments and have been extensively studied. This paper addresses a makespan minimisation scheduling problem on identical parallel machines, in which the specific processing time of each job is uncertain, and its probability distribution is unknown because of limited information. In this case, the deterministic or stochastic scheduling model may be unsuitable. We propose a robust (min–max regret) scheduling model for identifying a robust schedule with minimal maximal deviation from the corresponding optimal schedule across all possible job-processing times (called scenarios). These scenarios are specified as closed intervals. To solve the robust scheduling problem, which is NP-hard, we first prove that a regret-maximising scenario for any schedule belongs to a finite set of extreme point scenarios. We then derive two exact algorithms to optimise this problem using a general iterative relaxation procedure. Moreover, a good initial solution (optimal schedule under a mid-point scenario) for the aforementioned algorithms is discussed. Several heuristics are developed to solve large-scale problems. Finally, computational experiments are conducted to evaluate the performance of the proposed methods.     

A combined supply chain optimisation model for the installation phase of offshore wind projects

This paper proposes a combined model for port selection and supply chain optimisation for the installation phase of an offshore wind farm. Two strategic models are proposed where the first model, based on Analytical Hierarchy Process (AHP), aims to select the most suitable installation port. The second model is developed using Integer Linear Programming (ILP) in order to determine the optimal transportation schedule of the components from suppliers to the chosen installation port. The proposed models are evaluated for the West Gabbard (UK) offshore wind farm located in southern part of the North Sea. According to the computational results, the AHP model chooses port of Oostende, Belgium as the most suitable installation port for this offshore wind farm whereas the proposed supply chain model shows that the total transportation cost makes up 9% of total supply chain cost.     

Value chain management for commodities: a case study from the chemical industry

We present a planning model for chemical commodities related to an industry case. Commodities are standard chemicals characterized by sales and supply volatility in volume and value. Increasing and volatile prices of crude oil-dependent raw materials require coordination of sales and supply decisions by volume and value throughout the value chain to ensure profitability. Contract and spot demand differentiation with volatile and uncertain spot prices, spot sales quantity flexibility, spot sales price–quantity functions and variable raw material consumption rates in production are problem specifics to be considered. Existing chemical industry planning models are limited to production and distribution decisions to minimize costs or makespan. Demand-oriented models focus on uncertainty in demand quantities not in prices. We develop an integrated model to optimize profit by coordinating sales quantity, price and supply decisions throughout the value chain. A two-phase optimization approach supports robust planning ensuring minimum profitability even in case of worst-case spot sales price scenarios. Model evaluations with industry case data demonstrate the impact of elasticities, variable raw material consumption rates and price uncertainties on planned profit and volumes.     

一种面向卷烟混合生产线的优化调度模型研究

目的 基于多品种、小批量的生产制造模式,在规定的8 h工作之内,快速有效地生产出多品种、多批量的卷烟,并对所需物料进行准确调度,达到经济效益最大化的目的。方法 针对某烟草生产企业订单需要生产6种型号的品牌香烟,通过分析卷烟生产线的工艺流程,提出一种解决卷烟厂车间资源优化调度的CSS模型,该模型可以根据产品之间的销售需求情况来匹配生产线资源配置,按需求比采用粒子群优化算法计算出单次投料后混合生产香烟所需的最小时间与最大收益。结果 将所得方案进行综合对比后,计算得出在规定工期内,生产香烟获取利益的最优分配方案,在迭代在10次以内时已完成了优化过程,最大获利为3.65万元。结论 该优化模型通过改变相关工艺参数能够实现对不同混合生产线的资源调度优化,并对其他制造行业提供借鉴价值。     

多项目关键链进度优化算法分析

针对多项目进度优化问题,综合应用关键链和社会认知优化算法,保证了多项目计划在不确定环境下的稳定运行。文章首先在保证进度工期最短的前提下,进行了多项目的排序,进而确定对后续项目的影响。通过实例应用于多项目进度管理中,为工程决策与管理者全面而准确地进行多项目管理、掌握项目进度、保证项目如期完工,以及对后续项目进行合理地预测提供了依据。并讨论了应用关键链方法进一步研究的方向。     

Stability and resource allocation in project planning

The majority of resource-constrained project scheduling efforts assume perfect information about the scheduling problem to be solved and a static deterministic environment within which the precomputed baseline schedule is executed. In reality, project activities are subject to considerable uncertainty, which generally leads to numerous schedule disruptions. In this paper, we present a resource allocation model that protects a given baseline schedule against activity duration variability. A branch-and-bound algorithm is developed that solves the proposed resource allocation problem. We report on computational results obtained on a set of benchmark problems.     

An optimization model for a crop deficit irrigation system under uncertainty

In this study, an inexact nonlinear programming model under uncertainty is developed by incorporating a water production function into the crop irrigation system optimization framework. By introducing a time parameter, this model can address the uncertainty associated with the irrigation schedule for different crops and their planting stages. The developed model was applied to a case study of an agricultural water resources management problem to demonstrate its applicability. Through scenario analysis under different precipitation levels, the key planting stage of crops and the amount of water for the irrigation schedule that could significantly affect system benefits were identified. By using intervals to represent uncertain parameters, more reliable and practical decision alternatives were generated through the presented model in typical hydrological years (i.e. wet, normal and dry years).     

Flow shop scheduling with grid-integrated onsite wind power using stochastic MILP

Over the last decade, manufacturing companies have identified renewable energy as a promising means to cope with time-varying energy prices and to reduce energy-related greenhouse gas emissions. As a result of this development, global installed capacity of wind power has expanded significantly. To make efficient use of onsite wind power generation facilities in manufacturing, production scheduling tools need to consider the uncertainty attached to wind power generation along with changes in the energy procurement cost and in the products’ environmental footprints. To this end, we propose a solution procedure that first generates a large number of wind power scenarios that characterise the variability in wind power over time. Subsequently, a two-stage stochastic optimisation procedure computes a production schedule and energy supply decisions for a flow shop system. In the first stage, a bi-objective mixed integer linear programme simultaneously minimises the total weighted flow time and the expected energy cost, based on the generated wind power scenarios. In the second stage, energy supply decisions are adjusted based on real-time wind power data. A numerical example is used to illustrate the ability of the developed decision support tool to handle the uncertainty attached to wind power generation and its effectiveness in realising energy-related objectives in manufacturing.     

基于优先规则的模糊资源受限多项目调度

在分析国内外相关研究现状的基础上,结合资源受限多项目调度问题的特点,针对多项目中各个工序资源参数的不确定性,通过对工程项目工序资源需求量的模糊表示,建立了模糊资源受限多项目调度模型,并运用基于优先规则的启发式算法对所建立的模型进行调度计算,最后通过算例验证模型的有效性和可行性,以实现多项目资源的优化配置。     

Shift scheduling for steppers in the semiconductor wafer fabrication process

In this paper, an approach is proposed for scheduling stepper machines that are acting as bottleneck machines in the semiconductor wafer fabrication process. We consider the problem of scheduling the steppers for an 8 hour shift, determining which types of wafer lots to work on each machine. The scheduling objective is to find the optimal stepper allocations such that the schedule meets target production quantities that have been derived from the given target Work-In-Process (WIP) levels. A Mixed Integer Programming (MIP) model is formulated, and three heuristic approaches are proposed and tested to approximately solve the M1P model. Numerical tests show that one of the proposed heuristics using linear programming relaxation of MIP generates, on average, schedules within 5° of the optimum values.     

物料需求计划不稳定性的模拟研究

介绍物料需求计划不稳定性的基本概念和模拟研究方法。在不确定性需求的流动式计划环境下,研究冻结参数和计划算法在不同生产条件下对物料需求计划不稳定性的影响。通过设计模拟实验和大量模拟计算及统计分析表现：费用结构、预测模式、冻结比例、计划周期和计划算法对物料需求计划不稳定性有较大影响,且交互作用显著。研究结果对减小物料需求计划的不稳定性有一定指导意义。     

Robust single machine scheduling with uncertain release times for minimising the maximum waiting time

We study a single machine scheduling problem (SMSP) with uncertain job release times (JRTs) under the maximum waiting time (MWT) criterion. To deal with the uncertainty, a robust model is established to find an optimal schedule, which minimises the worst-case MWT (W-MWT) when JRTs vary over given time intervals. Although infinite possible scenarios for JRTs exist, we show that only n scenarios are needed for calculating the W-MWT, where n is the number of jobs. Based on this property, the robust (SMSP) with uncertain JRTs to minimise the W-MWT is formulated as a mixed integer linear programming problem. To solve large-size problem instances, an efficient two-stage heuristic (TSH) is proposed. In the first stage, n near-optimal schedules are obtained by solving n deterministic scenario-based SMSPs, and their W-MWTs are evaluated. To speed up the solution and evaluation process, a modified Gusfield’s heuristic is proposed by exploiting the inner connections of these SMSPs. To further improve the schedule obtained in the first stage, the second stage consists of a variable neighbourhood search method by combining both swap neighbourhood search and insert neighbourhood search. We also develop a method to calculate the lower bound of the proposed model so that we can evaluate the performance of the solutions given by the TSH. Experimental results confirm the robustness of schedules produced and advantages of the proposed TSH over other algorithms in terms of solution quality and run time.     

Robust optimization applied to uncertain production loading problems with import quota limits under the global supply chain management environment

Global supply chain management presents some special challenges and issues for manufacturing companies in planning production: these challenges are different from those discussed in domestic production plans. Globally loading production among different plants usually involves substantial uncertainty and great risk because of uncertain market demand, fluctuating quota costs incurred in the global manufacturing process, and shortening lead times. This study proposes a dual-response production loading strategy for two types of plants—company-owned and contracted—to hedge against the short lead time and uncertainty, and to be as responsive and flexible as possible to cope with the uncertainty and risk involved. Three types of robust optimization models are presented: the robust optimization model with solution robustness, the robust optimization model with model robustness, and the robust optimization model with the trade-off between solution robustness and model robustness. A series of experiments are designed to test the effectiveness of the proposed robust optimization models. Compared with the results of the two-stage stochastic recourse programming model, the robust optimization models provide a more responsive and flexible system with less risk, which is particularly important in the current context of global competitiveness.