面向订单的生产计划与调度的综合优化

研究了一个多订单环境下的生产计划与调度集成优化问题,以实现准时生产为目标,综合考虑产品装配结构约束的订单任务计划与订单产品零部件的加工调度,采用直接面向客户订单的工序调度模式建立了计划和调度的综合优化整数规划模型.设计了带精英策略的蚁群算法作为该数学模型的求解方法,并通过对比试验为该算法选取最佳的搜索参数.实例仿真结果表明,所建模型的正确性以及蚁群算法求解该问题的可行性和有效性.     

Capacitated disassembly scheduling with random demand

This paper considers disassembly scheduling, which is the problem of determining the quantity and timing of the end-of-use/life products to be disassembled while satisfying the demand for their parts obtained from disassembling the products over a planning horizon. This paper focuses on the problem with stochastic demand of parts/modules, capacity restrictions on disassembly resources, and multiple product types with a two-level product structure. The two-level product structure implies that an end-of-use/life product is hierarchically decomposed into two levels where the first level corresponds to the parts/modules and the second level corresponds to the product. We formulate the problem as a stochastic inventory model and to solve the problem we propose a Lagrangian heuristic algorithm as well as an optimisation algorithm for the sub-problems obtained from Lagrangian decomposition. The test results on randomly generated problems show that the Lagrangian heuristic algorithm demonstrates good performance in terms of solution quality and time.     

Distributed optimisation method for multi-resource constrained scheduling in coal supply chains

We consider an integrated planning and scheduling problem motivated by the coal supply chains in Australia. The problem considers production planning of several independent mines. The mines need trains to complete delivery of coal by the arrival of ships at the terminal. The trains, on the other hand, are in limited supply and therefore the mines need to share this common resource. For this problem, we present a mixed integer programming formulation which minimises total weighted earliness, tardiness and operational costs. We also present a distributed algorithm based on the Lagrangian relaxation, which incorporates the volume and Wedelin algorithms. The strength of our distributed algorithm is demonstrated by an extensive computational experiment on several randomly generated instances.     

Advanced planning and scheduling based on precedence and resource constraints for e-plant chains

The e-plant chain is an extension of the integration beyond a production site by means of improved distribution management, electronic data interchange and coordination of multiple plants. The present paper proposes an advanced planning and scheduling model for the e-plant chain. The advanced planning and scheduling is the most important function when supporting flexible planning and scheduling in the e-plant chain. The problem is formulated as a mixed integer-programming model. The model includes the main features of the system including flexible operations’?sequences, resource requirements and alternative schedules. Since the problem is NP-hard, an intelligent search approach based on a genetic algorithm is developed. Numerical experiments show the proposed approach is satisfactory in its accuracy and efficiency.     

Multi-objective process planning and scheduling using controlled elitist non-dominated sorting genetic algorithm

The integration of process planning and scheduling is considered as a critical component in manufacturing systems. In this paper, a multi-objective approach is used to solve the planning and scheduling problem. Three different objectives considered in this work are minimisation of makespan, machining cost and idle time of machines. To solve this integration problem, we propose an improved controlled elitist non-dominated sorting genetic algorithm (NSGA) to take into account the computational intractability of the problem. An illustrative example and five test cases have been taken to demonstrate the capability of the proposed model. The results confirm that the proposed multi-objective optimisation model gives optimal and robust solutions. A comparative study between proposed algorithm, controlled elitist NSGA and NSGA-II show that proposed algorithm significantly reduces scheduling objectives like makespan, cost and idle time, and is computationally more efficient.     

A multi-objective optimisation model to integrating flexible process planning and scheduling based on hybrid multi-objective simulated annealing

Process planning and production scheduling play important roles in manufacturing systems. In this paper we present a mixed integer linear programming (MILP) scheduling model, that is to say a slot-based multi-objective multi-product, that readily accounts for sequence-dependent preparation times (transition and set up times or machine changeover time). The proposed scheduling model becomes computationally expensive to solve for long time horizons. The aim is to find a set of high-quality trade-off solutions. This is a combinatorial optimisation problem with substantially large solution space, suggesting that it is highly difficult to find the best solutions with the exact search method. To account for this, the hybrid multi-objective simulated annealing algorithm (MOHSA) is proposed by fully utilising the capability of the exploration search and fast convergence. Two numerical experiments have been performed to demonstrate the effectiveness and robustness of the proposed algorithm.     

Capacitated disassembly scheduling with parts commonality and start-up cost and its industrial application

This paper discusses the capacitated disassembly scheduling with parts commonality and start-up cost, which has broad applications in remanufacturing and many other production systems. The problem is formulated as a mixed-integer programming model. A Lagrangian heuristic is developed, where the lower bound problem reduces to a linear model, and the upper bound can be obtained with a two-stage procedure in polynomial time. The algorithm is tested on randomly generated problems. The results reveal that the approach outperforms CPLEX significantly for all the test instances, and for real-scale problem it provides sufficiently good solutions within acceptable time. Sensitivity studies on capacity, parts commonality and start-up cost are also conducted, which provide some useful insights for industrial managers. Moreover, a real-world case from a valve disassembly factory is studied, which illustrates the application of the proposed approach and gives managerial insights. Finally, conclusions are drawn and some potential extensions are discussed.     

求解带AGV柔性作业车间调度问题的改进灰狼算法

针对带AGV的柔性作业车间调度问题,以最小化完工时间为目标,考虑AGV在装载站、机器、卸载站之间的有效负载时间和空载时间,构建了数学规划模型。其次,提出一种有效的灰狼算法进行求解,基于该问题特征,设计机器选择、工序排序和AGV搬运的3段编码,有效地保证每个个体均可产生可行解;灰狼算法中改进了关键参数a和E设定方式,有效平衡了算法的勘探能力和局部搜索能力;为进一步提升算法跳出局部最优解的能力,该算法融合了领域搜索等方法。最后,案例测试结果表明,改进灰狼算法在求解带AGV柔性作业车间调度问题中具有优越的性能。     

Deep Reinforcement Learning-Based Job Shop Scheduling ofSmartManufacturing

Industry 4.0 production environments and smart manufacturing systems integrate both the physical and decision-making aspects of manufacturing operations into autonomous and decentralized systems. One of the key aspects of these systems is a production planning, specifically, Scheduling operations on the machines. To cope with this problem, this paper proposed a Deep Reinforcement Learning with an Actor-Critic algorithm (DRLAC). We model the Job-Shop Scheduling Problem (JSSP) as a Markov Decision Process (MDP), represent the state of a JSSP as simple Graph Isomorphism Networks (GIN) to extract nodes features during scheduling, and derive the policy of optimal scheduling which guides the included node features to the best next action of schedule. In addition, we adopt the Actor-Critic (AC) network’s training algorithm-based reinforcement learning for achieving the optimal policy of the scheduling. To prove the proposed model’s effectiveness, first, we will present a case study that illustrated a conflict between two job scheduling, secondly, we will apply the proposed model to a known benchmark dataset and compare the results with the traditional scheduling methods and trending approaches. The numerical results indicate that the proposed model can be adaptive with real-time production scheduling, where the average percentage deviation (APD) of our model achieved values between 0.009 and 0.21 compared with heuristic methods and values between 0.014 and 0.18 compared with other trending approaches.     

A random-key encoded harmony search approach for energy-efficient production scheduling with shared resources

When seeking near-optimal solutions for complex scheduling problems, meta-heuristics demonstrate good performance with affordable computational effort. This has resulted in a gravitation towards these approaches when researching industrial use-cases such as energy-efficient production planning. However, much of the previous research makes assumptions about softer constraints that affect planning strategies and about how human planners interact with the algorithm in a live production environment. This article describes a job-shop problem that focuses on minimizing energy consumption across a production facility of shared resources. The application scenario is based on real facilities made available by the Irish Center for Manufacturing Research. The formulated problem is tackled via harmony search heuristics with random keys encoding. Simulation results are compared to a genetic algorithm, a simulated annealing approach and a first-come-first-served scheduling. The superior performance obtained by the proposed scheduler paves the way towards its practical implementation over industrial production chains.     

Advanced production scheduling for batch plants in process industries

An Advanced Planning System (APS) offers support at all planning levels along the supply chain while observing limited resources. We consider an APS for process industries (e.g. chemical and pharmaceutical industries) consisting of the modules network design (for long–term decisions), supply network planning (for medium–term decisions), and detailed production scheduling (for short–term decisions). For each module, we outline the decision problem, discuss the specifi cs of process industries, and review state–of–the–art solution approaches. For the module detailed production scheduling, a new solution approach is proposed in the case of batch production, which can solve much larger practical problems than the methods known thus far. The new approach decomposes detailed production scheduling for batch production into batching and batch scheduling. The batching problem converts the primary requirements for products into individual batches, where the work load is to be minimized. We formulate the batching problem as a nonlinear mixed–integer program and transform it into a linear mixed–binary program of moderate size, which can be solved by standard software. The batch scheduling problem allocates the batches to scarce resources such as processing units, workers, and intermediate storage facilities, where some regular objective function like the makespan is to be minimized. The batch scheduling problem is modelled as a resource–constrained project scheduling problem, which can be solved by an efficient truncated branch–and–bound algorithm developed recently. The performance of the new solution procedures for batching and batch scheduling is demonstrated by solving several instances of a case study from process industries.     

Remanufacturing-oriented process planning and scheduling: mathematical modelling and evolutionary optimisation

Remanufacturing has been widely studied for its potential to achieve sustainable production in recent years. In the literature of remanufacturing research, process planning and scheduling are typically treated as two independent parts. However, these two parts are in fact interrelated and often interact with each other. Doing process planning without considering scheduling related factors can easily introduce contradictions or even infeasible solutions. In this work, we propose a mathematical model of integrated process planning and scheduling for remanufacturing (IPPSR), which simultaneously considers the process planning and scheduling problems. An effective hybrid multi-objective evolutionary algorithm (HMEA) is presented to solve the proposed IPPSR. For the HMEA, a multidimensional encoding operator is designed to get a high-quality initial population. A multidimensional crossover operator and a multidimensional mutation operator are also proposed to improve the convergence speed of the algorithm and fully exploit the solution space. Finally, a specific legalising method is used to ‘legalise’ possible infeasible solutions generated by the initialisation method and mutation operator. Extensive computational experiments carried out to compare the HMEA with some well-known algorithms confirm that the proposed HMEA is able to obtain more and better Pareto solutions for IPPSR.     

Iterated beam search for the combined car sequencing and level scheduling problem

The level scheduling problem is concerned with the final stage of a multi-stage just-in-time production system so that different models of a product are evenly distributed in a discrete production sequence, thereby making the problem practically an unconstrained optimisation problem. The car sequencing problem, on the other hand, is a constraint satisfaction problem based on a number of options constricting the final assembly schedule. The combined car sequencing and level scheduling problem aims to find the optimal production schedule that evenly distributes different models over the planning horizon and satisfies all option constraints. This paper proposes a parametric iterated beam search algorithm for the combined problem that can be used either as a heuristic or as an exact optimisation method. The paper includes a computational study based on a 54-instance test bed that proves the effectiveness of the proposed algorithm.     

Simultaneous Lot Sizing and Sequencing for Multistage Production Systems

Inventory and scheduling theory have, in general, been developed independently. This paper presents a model which integrates these two traditionally different aspects of production planning in a multi-stage environment by transforming a lot-sizing problem to an equivalent job-shop scheduling program. The proposed model may improve the effectiveness of existing decision making processes.     

Optimal scheduling of logistical support for an emergency roadway repair work schedule

The completion of every disaster rescue task performed by repair work teams relies on the in-time supply of materials to the rescue workers. Up to now, logistical support planning for emergency repair work in Taiwan has been done manually, which is neither effective nor efficient. To remedy the problem, this study presents a logistical support scheduling model for the given emergency repair work schedule. The objective is to minimize the short-term operating cost subject to time constraints and other related operating constraints. This model is formulated as an integer multiple-commodity network flow problem which is characterized as NP-hard. A heuristic algorithm, based on the problem decomposition and variable fixing techniques, is also proposed to efficiently solve this problem. Computational tests are performed using data from Taiwan's 1999 Chi-Chi earthquake. The results show that the model and the solution algorithm would be useful for the logistical support scheduling.     

Two-stage stochastic master production scheduling under demand uncertainty in a rolling planning environment

This paper proposes a scenario-based two-stage stochastic programming model with recourse for master production scheduling under demand uncertainty. We integrate the model into a hierarchical production planning and control system that is common in industrial practice. To reduce the problem of the disaggregation of the master production schedule, we use a relatively low aggregation level (compared to other work on stochastic programming for production planning). Consequently, we must consider many more scenarios to model demand uncertainty. Additionally, we modify standard modelling approaches for stochastic programming because they lead to the occurrence of many infeasible problems due to rolling planning horizons and interdependencies between master production scheduling and successive planning levels. To evaluate the performance of the proposed models, we generate a customer order arrival process, execute production planning in a rolling horizon environment and simulate the realisation of the planning results. In our experiments, the tardiness of customer orders can be nearly eliminated by the use of the proposed stochastic programming model at the cost of increasing inventory levels and using additional capacity.     

A hybrid flowshop scheduling problem for a cold treating process in seamless steel tube production

Seamless steel tubes often have various categories and specifications, which further require complicated operations in production, especially in the cold treating process (CTP). This paper investigates the scheduling problem using the seamless tube plant of Baoshan Iron and Steel Complex as a study background. By considering the practical production constraints such as sequence-dependent setup times, maintenance schedule, intermediate material buffers, job-machine matches, we formulate the hybrid flowshop scheduling problem with a non-linear mixed integer programming model (NMIP). In addition, our model provides a flexibility to remove the permutation assumption, which is often a limitation in early studies. In order to obtain the solution of the above NMIP problem, a two-stage heuristic algorithm is proposed and it combines a modified genetic algorithm and a local search method. With real production instances, our computation experiments indicate that the proposed algorithm is efficient and it outperforms several other approaches. Industrial implementation also shows that such a scheduling tool brings a cost saving of more than 10% and it substantially reduces the computation time. Our study also illustrates the need of relaxing permutation assumption in such a scheduling problem with complicated operation sequences.     

Dynamic scheduling of production-assembly networks in a distributed environment

In complex manufacturing environments, meeting the due dates of the jobs and minimizing in process inventories are important performance metrics. One of the common characteristics of complex production systems is production-assembly network of operations. This paper presents an auction-based algorithm for simultaneous scheduling of all manufactured and assembled jobs in a dynamic environment, where the objective function is to minimize both the due date penalties associated with the final products and the inventory cost of the work in process. An auction-based approach using a Mixed-Integer Linear Programming (MILP) model to construct and evaluate the bids so that the auction mechanism mimics a Lagrangian relaxation-based subgradient optimization to ensure global optimality is proposed. The inner structure of the problem enables very efficient calculation of bids for each job or assembly. Using a full factorial experimental design the properties of the proposed algorithm are analyzed. Results show that the proposed auction based algorithm performs better than the popular dispatching rules and is more scalable than the MILP model or direct implementations of the subgradient algorithm. Furthermore, the proposed algorithm is designed to work in a dynamic environment.     

A coordinated algorithm for integrated production scheduling and vehicle routing problem

In this paper, the integrated production scheduling and vehicle routing problem is considered for a Make-to-Order manufacturer, who has a single machine for production and limited vehicles with capacity constraints for transportation. The objective is to determine production scheduling and vehicle routing, which are two interacted decisions, to minimise the maximum order delivery time. A property on optimal production sequence is proposed first, based on which backward and forward batching methods are developed and are embedded into a proposed genetic algorithm. The proposed genetic algorithm is capable of providing high-quality solutions by determining the two decisions simultaneously. For comparison purpose, a two-stage algorithm is developed, which decomposes the overall problem into two successively solved sub-problems. The experiments show that the proposed genetic algorithm can provide higher quality solutions than the proposed two-stage algorithm and two published algorithms studying related problems.     

复杂型面智能生产单元任务−刀具联合动态调度策略

以复杂型面智能生产单元为背景,针对多机器的任务?刀具联合动态调度问题展开研究。通过分析复杂型面智能生产单元的作业流程和特征,建立任务?刀具联合调度问题的数学模型。结合通过对问题进行过程分解的方式构建一种组合规则调度算法生产框架,并通过在框架中嵌入启发式规则的方式生成72种组合规则算法。设计大量的算例测试集,通过对比、分析72种算法在差异化环境配置下的仿真结果,对比不同系统指标下算法的表现情况,发现基于FNOP规则构建的算法在75%的场景中均能取得较优的求解质量。研究成果为车间生产管理人员制定任务?刀具调度策略提供一定指导作用。