A heuristic relief transportation planning algorithm for emergency supply chain management

Emergency supply chain operations have to fulfil all the demands in a very short period of time, using the limited resources at its disposal. Mixed integer programming (MIP) is a popular method to solve emergency supply chain planning problems. However, as such problem increases in complexity, the MIP model becomes insolvable due to the time and computer resources it requires. This study proposes a heuristic algorithm, called the Emergency Relief Transportation Planning Algorithm (ERTPA). ERTPA will group and sort demands according to the required products, the imposed due dates, the possible shared capacities, and the distances from the demand nodes to the depots. Then, ERTPA plans the demands individually, using a shortest travelling-time tree and a minimum cost production tree. To show the effectiveness and efficiency of the heuristic algorithm, a prototype was constructed and tested, using complexity and computational analyses.     

Solving mixed integer programming production planning problems with setups by shadow price information

Algorithms developed to solve linear programming (LP) problems and advances in computer speed have made large-scale LP problems solvable in time for implementation. Solving an LP is relatively easier than solving an MIP for modern production planning problems. In this study, we propose a heuristic iterative algorithm between LP solution phases and setup decision computations for solving these difficult MIP production planning problems. By utilizing the shadow price information provided by the LP solution of the previous iteration, the setup decision computation converts an MIP problem into an LP problem, which can be efficiently solved in the current iteration. Extensive experiments show that the proposed heuristic algorithm performs well.     

A heuristic algorithm for master planning that satisfies multiple objectives

This study proposes a heuristic algorithm, called the multi-objective master planning algorithm (MOMPA), to solve master planning (MP) problems for a supply chain network with multiple finished products. MOMPA has three objectives: to minimize delay penalties, to minimize use of outsourcing capacity, and to minimize the costs of materials, production, processing, transportation, and inventory holding—all while respecting the capacity limitations and the demand deadlines of all those involved in a given supply chain network. MOMPA plans each demand, one by one, without backtracking, and sorts those demands using a sorting mechanism that is part of the algorithm. For each demand, the minimum production cost tree is determined within the limits of the time bucket for the demand deadline. The maximum available capacity of this tree is then computed for the “no delay” case. Following this calculation, the delay-or-not criterion is evaluated to determine whether or not further delay is necessary. MOMPA compares the results of these two procedures and allocates the appropriate capacities to the demand for all the nodes on the selected tree. If the minimum cost production tree has no available capacity, MOMPA adjusts the network and looks for a new tree. With complexity and computational analysis, MOMPA is shown to be very efficient in solving MP problems, sometimes generating the same optimal solution as the LP model.     

A cutting plane approach for integrated planning and scheduling

In this paper we propose a branch-and-cut algorithm for solving an integrated production planning and scheduling problem in a parallel machine environment. The planning problem consists of assigning each job to a week over the planning horizon, whereas in the scheduling problem those jobs assigned to a given week have to be scheduled in a parallel machine environment such that all jobs are finished within the week. We solve this problem in two ways: (1) as a monolithic mathematical program and (2) using a hierarchical decomposition approach in which only the planning decisions are modeled explicitly, and the existence of a feasible schedule for each week is verified by using cutting planes. The two approaches are compared with extensive computational testing.     

A heuristic master planning algorithm for supply chains that consider substitutions and commonalities

This study focuses on solving the master planning problem for supply chains by considering substitutions and common components. Such problems address the difficulties involved in synchronizing manufacturing processes and transporting of materials, semi-finished products, and final products along a supply chain and facilitate decision-making related to the effective and efficient use of production and transportation capacities over periods ranging from one month to one year. This study considers product structures with multiple final products, given substitutions and common components. For situations in which the capacity of the supply chain network partners is limited, the model constructed in this study is able to plan all demands and minimize delay costs, substitutions, and the costs of production, transportation, substitution, and inventory holding. Mixed integer programming is a popular way to solve supply chain master planning problems. However, as such problems increase in complexity, the MIP model becomes insolvable due to the time and computer resources it requires. Therefore, this study proposes a heuristic algorithm, called the Dynamic Search BOM Substitution Algorithm (DSBSA), to solve the supply chain master planning problem efficiently and effectively. DSBSA sorts demands according to the necessary final products, due dates, shared capacities, and substitution conditions, to name several possible criteria. Then, DSBSA plans the demands individually, using a minimum cost production tree. If the demand cannot be filled completely using the original BOMs (Bill of Materials), DSBSA substitutes another BOM to fill the demands. This study develops two algorithms to search the substitute BOM: one searches for substitutions in the BOM’s materials levels, this maintaining most of the materials in the original BOM; the other searches for substitutions and uses them to fill bottlenecks, allowing insufficient levels of materials to be detected and supplemented. To show the effectiveness and efficiency of DSBSA, a prototype was constructed and tested to demonstrate the power of DSBSA using complexity and computational analysis.     

基于柔性维护的堕化单机系统调度研究

针对单机系统,在假设生产系统为堕化系统,且生产过程中作业的加工不可中断的情况下,对考虑柔性时间窗口[[u,v]]下进行长度为[w]的周期预防性维护的调度问题进行了研究。建立了综合考虑生产调度和设备维护的混合整数规划模型,并设计了一套基于贪婪的启发式算法对所研究问题进行优化求解。通过Cplex和启发式算法求解结果的对比证明了算法可以快速、有效地解决此类问题。     

Using tabu search with ranking candidate list to solve production planning problems with setups

This study considers production planning problems involving multiple products, multiple resources, multiple periods, setup times, and setup costs. It can be formulated as a mixed integer program (MIP). Solving a realistic MIP production planning problem is NP-hard; therefore, we use tabu search methods to solve such a difficult problem. Furthermore, we improve tabu search by a new candidate list strategy, which sorts the neighbor solutions using post-optimization information provided by the final tableau of the linear programming simplex algorithm. A neighbor solution with higher priority in the ranking sequence has a higher probability of being the best neighbor solution of a current solution. According to our experiments, the proposed candidate list strategy tabu search produces a good solution faster than the traditional simple tabu search. This study also suggests that if the evaluation of the entire neighborhood space in a tabu search algorithm takes too much computation and if an efficient and effective heuristic to rank the neighbor solutions can be developed, the speed of tabu search algorithm could be significantly increased by using the proposed candidate list strategy.     

Efficient solution of the 3G network planning problem

The 3G universal mobile telecommunications system (UMTS) planning problem is combinatorially explosive and difficult to solve optimally, though solution methods exist for its three main subproblems (cell, access network, and core network planning). We previously formulated the entire problem as a single integrated mixed-integer linear program (MIP) and showed that only small instances of this global planning problem can be solved to optimality by a commercial MIP solver within a reasonable amount of time ( St-Hilaire, Chamberland, & Pierre, 2006). Heuristic methods are needed for larger instances. This paper provides the first complete formulation for the heuristic sequential method ( St-Hilaire, Chamberland, & Pierre, 2005) that re-partitions the global formulation into the three conventional subproblems and solves them in sequence using a MIP solver. This greatly improves the solution time, but at the expense of solution quality. We also develop a new hybrid heuristic that uses the results of the sequential method to generate constraints that provide tighter bounds for the global planning problem with the goal of reaching the provable optimum solution much more quickly. We empirically evaluate the speed and solution accuracy of four solution methods: (i) the direct MIP solution of the global planning problem, (ii) a local search heuristic applied to the global planning problem, (iii) the sequential method and (iv) the new hybrid method. The results show that the sequential method provides very good results in a fraction of the time needed for the direct MIP solution of the global problem, and that optimum results can be provided by the hybrid heuristic in greatly reduced time.     

Adaptive genetic algorithm for advanced planning in manufacturing supply chain

A main function for supporting global objectives in a manufacturing supply chain is planning and scheduling. This is considered such an important function because it is involved in the assignment of factory resources to production tasks. In this paper, an advanced planning model that simultaneously decides process plans and schedules was proposed for the manufacturing supply chain (MSC). The model was formulated with mixed integer programming, which considered alternative resources and sequences, a sequence-dependent setup and transportation times.The objective of the model was to analyze alternative resources and sequences to determine the schedules and operation sequences that minimize makespan. A new adaptive genetic algorithm approach was developed to solve the model. Numerical experiments were carried out to demonstrate the efficiency of the developed approach. Received: June 2005 / Accepted: December 2005     

Minimizing cycle time and group scheduling, using Petri nets a study of heuristic methods

The objective of this paper is a study of minimizing the maximum completion time min F _max, or cycle time of the last job of a given family of jobs using flow shop heuristic scheduling techniques. Three methods are presented: minimize idle time (MIT); Campbell, Dudek and Smith (CDS); and Palmer. An example problem with ten jobs and five machines is used to compare results of these methods. A deterministic t-timed colored Petri net model has been developed for scheduling problem. An execution of the deterministic timed Petri net allows to compute performance measures by applying graph traversing algorithms starting from initial global state and going into a desirable final state(s) of the production system. The objective of the job scheduling policy is minimizing the cycle time of the last job scheduled in the pipeline of a given family of jobs. Three heuristic scheduling methods have been implemented. First, a sub-optimal sequence of jobs to be scheduled is generated. Second, a Petri net-based simulator with graphical user interface to monitor execution of the sequence of tasks on machines is dynamically designed. A deterministic t-timed colored Petri net model has been developed and implemented for flexible manufacturing systems (FMS). An execution of the deterministic timed Petri net into a reachability graph allows to compute performance measures by applying graph traversing algorithms starting from initial global state to a desirable final state(s) of the production system.     

混合遗传算法在柔性系统动态调度中的应用研究

本文研究了柔性制造系统实时生产环境下的动态调度问题.提出了基于动态数据库技术的动态调 度系统的框架结构.动态数据库中存储着问题的数据结构,包含工件相关类与机器相关类信息.动态数据库能 够随着生产的进行及时进行更新.扰动发生后,遗传算法根据动态数据库所提供的更新后的调度任务数据,快 速产生新的优化调度方案.通过在遗传算法中嵌入约束解决机制确保遗传算法适应约束的能力,从而提高算 法的收敛速度与精度.仿真实验证实了方案的有效性.     

Solving a multi-objective master planning problem with substitution and a recycling process for a capacitated multi-commodity supply chain network

This study focuses on solving the multi-objective master planning problem for supply chains by considering product structures with multiple final products using substitutions, common components, and recycled components. This study considers five objectives in the planning process: (1) minimizing the delay cost, (2) minimizing the substitution priority, (3) minimizing the recycling penalty, (4) minimizing the substitution cost, and (5) minimizing the cost of production, processing, inventory holding and transportation. This study proposes a heuristic algorithm, called the GA-based Master Planning Algorithm (GAMPA), to solve the supply-chain master planning problem efficiently and effectively. GAMPA first transforms the closed-loop supply chain into an open-loop supply chain that plans and searches the sub-networks for each final product. GAMPA then uses a genetic algorithm to sort and sequence the demands. GAMPA selects the chromosome that generates the best planning result according to the priority of the objectives. GAMPA plans each demand sequentially according to the selected chromosome and a randomly-selected production tree. GAMPA tries different production trees for each demand and selects the best planning result at the end. To show the effectiveness and efficiency of GAMPA, a prototype was constructed and tested using complexity analysis and computational analysis to demonstrate the power of GAMPA.     

Genetic algorithms in integrated process planning and scheduling

Process planning and scheduling are actually interrelated and should be solved simultaneously. Most integrated process planning and scheduling methods only consider the time aspects of the alternative machines when constructing schedules. The initial part of this paper describes a genetic algorithm (GA) based algorithm that only considers the time aspect of the alternative machines. The scope of consideration is then further extended to include the processing capabilities of alternative machines, with different tolerance limits and processing costs. In the proposed method based on GAs, the processing capabilities of the machines, including processing costs as well as number of rejects produced in alternative machine are considered simultaneously with the scheduling of jobs. The formulation is based on multi-objective weighted-sums optimization, which are to minimize makespan, to minimize total rejects produced and to minimize the total cost of production. A comparison is done w ith the traditional sequential method and the multi-objective genetic algorithm (MOGA) approach, based on the Pareto optimal concept.     

瓶颈指向的启发式算法求解混合流水车间调度问题

针对以最小化时间表长为目标的复杂混合流水车间调度问题,提出了一种将机器布局和工件加工时间特征紧密结合的启发式算法.首先,充分利用各阶段平均机器负荷一般不相等的特点确定瓶颈阶段,构建初始工件排序.其次,针对在瓶颈阶段前加工时间较短而瓶颈阶段后加工时间相对较长的工件,在第1阶段优先开始加工.同时,在瓶颈阶段前的每一个阶段,每当有工件等待加工或同时完工时,优先选择瓶颈阶段前剩余加工时间最短的工件加工;在瓶颈阶段以及瓶颈阶段之后,则优先选择这台机器后剩余加工时间最长的工件加工.最后,采用工件交换和插入操作改进初始调度.用Carlier和Neron的Benchmark算例测试提出的启发式算法.将计算结果与NEH启发式算法进行了比较,平均偏差降低了0.0555%,表明这个启发式算法是有效的.     

带有跨工序约束的柔性job shop调度问题*

飞机制造企业的金属加工车间是一种小批量、多品种生产,其生产指挥是一种带有跨工序约束的柔性job shop调度问题。针对这个NP-hard问题,提出一种三阶段启发式方法,通过依次完成瓶颈工作中心的判定、设备分配和任务排序,使这一问题的复杂度得以逐步降低,从而可以在多项式时间内得到有效的调度方案。实际运行表明,依据该启发式方法产生的调度方案,其关键路径的等待时间占总完工时间的比例不足1.5%,取得了满意的效果。     

Multiscale production routing in multicommodity supply chains with complex production facilities

In this work, we introduce the multiscale production routing problem (MPRP), which considers the coordination of production, inventory, distribution, and routing decisions in multicommodity supply chains with complex continuous production facilities. We propose an MILP model involving two different time grids. While a detailed mode-based production scheduling model captures all critical operational constraints on the fine time grid, vehicle routing is considered in each time period of the coarse time grid. In order to solve large instances of the MPRP, we propose an iterative MILP-based heuristic approach that solves the MILP model with a restricted set of candidate routes at each iteration and dynamically updates the set of candidate routes for the next iteration. The results of an extensive computational study show that the proposed algorithm finds high-quality solutions in reasonable computation times, and in large instances, it significantly outperforms a standard two-phase heuristic approach and a solution strategy involving a one-time heuristic pre-generation of candidate routes. Similar results are achieved in an industrial case study, which considers a real-world industrial gas supply chain.     

飞机排班调度中机组指派优化模型及算法研究

分析了航空企业飞机排班计划编制流程,重点研究了其中的空勤机组指派优化问题,建立了机组指派优化模型,模型同时考虑了机组与航班执行飞机之间在机型、飞行区域等条件上的匹配要求。为求解模型,构造了一种改进遗传算法,算法采用自然数编码,动态自适应调整交叉和变异概率,以及智能启发式规则修正的方式加快优化速度。采用航空公司的实际航班数据进行仿真实例研究结果表明,模型和算法切实可行。     

A hybrid Lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times

This paper examines the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times, time windows, machine eligibility and preference constraints. Such problems are quite common in the semiconductor manufacturing industry. In particular, this paper pays special attention to the chipset production in the semiconductor Assembly and Test Manufacturing (ATM) factory and constructs a Mixed Integer Programming (MIP) model for the problem. The primal problem is decomposed into a lot-sizing subproblem and a set of single-machine scheduling subproblems by Lagrangian decomposition. A Lagrangian-based heuristic algorithm, which incorporates the simulated annealing algorithm aimed at searching for a better solution during the feasibility construction stage, is proposed. Computational experiments show that the proposed hybrid algorithm outperforms other heuristic algorithms and meets the practical requirement for the tested ATM factory.     

Heuristic approaches for master planning in semiconductor manufacturing

In this paper, we propose heuristic approaches for solving master planning problems that arise in semiconductor manufacturing networks. The considered problem consists of determining appropriate wafer quantities for several products, facilities, and time periods by taking demand fulfillment (i.e., confirmed orders and forecasts) and capacity constraints into account. In addition, fixed costs are used to reduce production partitioning. A mixed-integer programming (MIP) formulation is presented and the problem is shown to be NP-hard. As a consequence, two heuristic procedures are proposed: a product based decomposition scheme and a genetic algorithm. The performance of both heuristics is assessed using randomly generated test instances. It turns out that the decomposition scheme is able to produce high-quality solutions, while the genetic algorithm achieves results with reasonable quality in a short amount of time.