A job shop distributed scheduling based on Lagrangian relaxation to minimise total completion time

This paper considers a distributed job shop scheduling problem where autonomous sub-production systems share common machines with each other. Each sub-production system is responsible for the scheduling of a set of jobs to minimise the total completion time on shared machines. A sub-production system has ultimate responsibility on maintaining private information such as objective function, processing time and routings on shared machines. Also sub-production systems must cooperate each other in order to achieve a global goal while sharing minimum of private information. In this research, we propose a distributed cooperation method in which sub-production systems and shared machines interact with one another to find a compromised solution between a locally optimised solution and a system-wide solution. We tested the proposed method for small, medium and large size of job shop scheduling problems and compared to a global optimal solutions. The proposed method shows promising results in terms of solution qualities and computational times.     

基于Q学习的任务调度问题的改进研究

论文针对协同工作中的任务调度问题,建立了相应的马尔可夫决策过程模型,在此基础上提出了一种改进的基于模拟退火的Q学习算法。该算法通过引入模拟退火,并结合贪婪策略,以及在状态空间上的筛选判断,显著地提高了收敛速度,缩短了执行时间。最后与其它文献中相关算法的对比分析,验证了本改进算法的高效性。     

Petri nets and genetic algorithms for complex manufacturing systems scheduling

In this paper we propose the GAPN (genetic algorithms and Petri nets) approach, which combines the modelling power of Petri nets with the optimisation capability of genetic algorithms (GAs) for manufacturing systems scheduling. This approach uses both Petri nets to formulate the scheduling problem and GAs for scheduling. Its primary advantage is its ability to model a wide variety of manufacturing systems with no modifications either in the net structure or in the chromosomal representation. In this paper we tested the performance on both classical scheduling problems and on a real life setting of a manufacturer of car seat covers. In particular, such a manufacturing system involves features such as complex project-like routings, assembly operations, and workstations with unrelated parallel machines. The implementation of the algorithm at the company is also discussed. Experiments show the validity of the proposed approach.     

Lagrangean relaxation approach to joint optimization for production planning and scheduling of synchronous assembly lines

This paper focuses on simultaneous optimisation of production planning and scheduling problem over a time period for synchronous assembly lines. Differing from traditional top-down approaches, a mixed integer programming model which jointly considers production planning and detailed scheduling constraints is formulated, and a Lagrangian relaxation method is developed for the proposed model, whereby the integrated problem is decomposed into planning, batch sequencing, tardiness and earliness sub-problems. The scheduling sub-problem is modelled as a time-dependent travelling salesman problem, which is solved using a dynasearch algorithm. A proposition of Lagrangian multipliers is established to accelerate the convergence speed of the proposed algorithm. The average direction strategy is employed to solve the Lagrangian dual problem. Test results demonstrate that the proposed model and algorithm are effective and 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.     

A genetic algorithm based approach for scheduling of jobs containing multiple orders in a three-machine flowshop

This paper investigates a new scheduling problem of multiple orders per job (MOJ) in a three-machine flowshop consisting of an item-processing machine, a lot-processing machine and a batch-processing machine, for a semiconductor manufacturing operation that must form a layer on the wafers. The three-machine flowshop MOJ scheduling problem deals with sequencing customer orders, assigning orders to jobs, and then combining the formed jobs into batches. Genetic algorithms are presented for this scheduling problem to minimise the total weighted tardiness (TWT), in the presence of non-zero order ready times, different order due dates, different order weights and unequal order sizes. Extensive experiments were performed to compare the proposed genetic algorithm (GA)-based approach with the benchmark heuristics presented in previous studies. The experiments led to the conclusions that the GA-based approach is significantly superior over other heuristics in terms of TWT and can find near-optimal solutions in an acceptable amount of computation time.     

Iterative algorithms for batching and scheduling to minimise the total job tardiness in two-stage hybrid flow shops

This study considers the batching and scheduling problem in two-stage hybrid flow shops in which each job with a distinct due-date is processed through two serial production stages, each of which has identical machines in parallel. Under the fundamental trade-off that large batch sizes with less frequent changeovers may reduce setup costs and hence increase machine utilisation, while small batch sizes may reduce job flow times and hence improve scheduling performance, the problem is to determine the number of batches, the batch compositions, the allocation of batches to the parallel machines at each stage, and the sequence of the batches allocated to each machine for the objective of minimising the total job tardiness. A mixed integer programming model is developed for the reduced problem in which the number of batches is given, and then, three iterative algorithms are proposed in which batching and scheduling are done repeatedly until a good solution is obtained. To show the performance of the algorithms, computational experiments were done on a number of test instances, and the results are reported. In particular, we show that the number of batches decreases as the ratio of the batch setup time to the job processing time increases.     

Lagrangian relaxation and cut generation for sequence-dependent setup time flowshop scheduling problems to minimise the total weighted tardiness

The Lagrangian relaxation and cut generation technique is applied to solve sequence-dependent setup time flowshop scheduling problems to minimise the total weighted tardiness. The original problem is decomposed into individual job-level subproblems that can be effectively solved by dynamic programming. Two types of additional constraints for the violation of sequence-dependent setup time constraints are imposed on the decomposed subproblems in order to improve the lower bound. The decomposed subproblem with the additional setup time constraints on any subset of jobs is also effectively solved by a novel dynamic programming. Computational results show that the lower bound derived by the proposed method is much better than those of CPLEX and branch and bound for problem instances with 50 jobs and five stages with less computational effort.     

Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems

Multi-factory production networks have increased in recent years. With the factories located in different geographic areas, companies can benefit from various advantages, such as closeness to their customers, and can respond faster to market changes. Products (jobs) in the network can usually be produced in more than one factory. However, each factory has its operations efficiency, capacity, and utilization level. Allocation of jobs inappropriately in a factory will produce high cost, long lead time, overloading or idling resources, etc. This makes distributed scheduling more complicated than classical production scheduling problems because it has to determine how to allocate the jobs into suitable factories, and simultaneously determine the production scheduling in each factory as well. The problem is even more complicated when alternative production routing is allowed in the factories. This paper proposed a genetic algorithm with dominant genes to deal with distributed scheduling problems, especially in a flexible manufacturing system (FMS) environment. The idea of dominant genes is to identify and record the critical genes in the chromosome and to enhance the performance of genetic search. To testify and benchmark the optimization reliability, the proposed algorithm has been compared with other approaches on several distributed scheduling problems. These comparisons demonstrate the importance of distributed scheduling and indicate the optimization reliability of the proposed algorithm.     

A new multi-objective optimization model for preventive maintenance and replacement scheduling of multi-component systems

In this article, a new multi-objective optimization model is developed to determine the optimal preventive maintenance and replacement schedules in a repairable and maintainable multi-component system. In this model, the planning horizon is divided into discrete and equally-sized periods in which three possible actions must be planned for each component, namely maintenance, replacement, or do nothing. The objective is to determine a plan of actions for each component in the system while minimizing the total cost and maximizing overall system reliability simultaneously over the planning horizon. Because of the complexity, combinatorial and highly nonlinear structure of the mathematical model, two metaheuristic solution methods, generational genetic algorithm, and a simulated annealing are applied to tackle the problem. The Pareto optimal solutions that provide good tradeoffs between the total cost and the overall reliability of the system can be obtained by the solution approach. Such a modeling approach should be useful for maintenance planners and engineers tasked with the problem of developing recommended maintenance plans for complex systems of components.     

Applying a hybrid simulated annealing and tabu search approach to non-permutation flowshop scheduling problems

Researchers have indicated that a permutation schedule can be improved by a non-permutation schedule in a flowshop with completion time-based criteria, such as makespan and total completion time. This study proposes a hybrid approach which draws on the advantages of simulated annealing and tabu search for the non-permutation flowshop scheduling problem, in which the objective function is the makespan of the schedule. To verify the effectiveness of the proposed hybrid approach, computational experiments are performed on a set of well-known non-permutation flowshop scheduling benchmark problems. The result shows that the performance of the hybrid approach is better than that of other approaches, including ant colony optimisation, simulated annealing, and tabu search. Further, the proposed approach found new upper bound values for all benchmark problems within a reasonable computational time.     

Single machine group scheduling with family setups to minimize total tardiness

This paper considers the single machine scheduling problem with independent family (group) setup times where jobs in each family are processed together. A sequence-independent setup is required to process a job from a different family. The objective is to minimize total tardiness. A mixed-integer linear programming model capable of solving small-sized problems is described. In view of the NP-hard nature of the problem, two-phase heuristics including simulated annealing algorithms are proposed to find optimal or near-optimal schedules. Empirical results show that the proposed heuristic algorithms are quite effective in minimizing total tardiness for a single machine group scheduling problem with family setup times.     

Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times

This paper focuses on an identical parallel machine scheduling problem with minimising total tardiness of jobs. There are two major issues involved in this scheduling problem; (1) jobs which can be split into multiple sub-jobs for being processed on parallel machines independently and (2) sequence-dependent setup times between the jobs with different part types. We present a novel mathematical model with meta-heuristic approaches to solve the problem. We propose two encoding schemes for meta-heuristic solutions and three decoding methods for obtaining a schedule from the meta-heuristic solutions. Six different simulated annealing algorithms and genetic algorithms, respectively, are developed with six combinations of two encoding schemes and three decoding methods. Computational experiments are performed to find the best combination from those encoding schemes and decoding methods. Our findings show that the suggested algorithm provides not only better solution quality, but also less computation time required than the commercial optimisation solvers.     

遗传算法的双目标柔性作业车间调度研究

研究了FMS环境下先进制造车间路径柔性的优化调度问题.同时考虑现代生产准时制的要求,建立了柔性作业车间调度问题的双目标数学优化模型,并给出了求解模型的遗传算法的具体实现过程;针对模型的特殊性,提出了染色体两层编码结构,将AOV网络图应用到解码和适应度函数的计算中,通过一个调度实例进行验证,给出了相应的选择、交叉、变异操作设计方案.     

Using simulated annealing to schedule a flowshop manufacturing cell with sequence-dependent family setup times

This paper proposes a simulated annealing-based meta-heuristic to minimise makespan in a flowshop manufacturing cell with sequence-dependent family setup times. To escape from local minima, Cauchy function?–?rather than the Boltzmann function?–?is used during the annealing process. The effectiveness and efficiency of the proposed simulated annealing-based meta-heuristic is compared against the existing heuristics on a benchmark problem dataset used in earlier studies. These computational results show that the proposed simulated annealing-based meta-heuristic is highly effective as compared to the state-of-the-art meta-heuristics for this problem on the same benchmark instances.     

Mathematical modelling and a meta-heuristic for flexible job shop scheduling

This study develops new solution methodologies for the flexible job shop scheduling problem (F-JSSP). As a first step towards dealing with this complex problem, mathematical modellings have been used; two novel effective position- and sequence-based mixed integer linear programming (MILP) models have been developed to fully characterise operations of the shop floor. The developed MILP models are capable of solving both partially and totally F-JSSPs. Size complexities, solution effectiveness and computational efficiencies of the developed MILPs are numerically explored and comprehensively compared vis-à-vis the makespan optimisation criterion. The acquired results demonstrate that the proposed MILPs, by virtue of its structural efficiencies, outperform the state-of-the-art MILPs in literature. The F-JSSP is strongly NP-hard; hence, it renders even the developed enhanced MILPs inefficient in generating schedules with the desired quality for industrial scale problems. Thus, a meta-heuristic that is a hybrid of Artificial Immune and Simulated Annealing (AISA) Algorithms has been proposed and developed for larger instances of the F-JSSP. Optimality gap is measured through comparison of AISA’s suboptimal solutions with its MILP exact optimal counterparts obtained for small- to medium-size benchmarks of F-JSSP. The AISA’s results were examined further by comparing them with seven of the best-performing meta-heuristics applied to the same benchmark. The performed comparative analysis demonstrated the superiority of the developed AISA algorithm. An industrial problem in a mould- and die-making shop was used for verification.     

Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness

This paper studies the problem of scheduling flexible job shops with setup times where the setups are sequence-dependent. The objective is to find the schedule with minimum total tardiness. First, the paper develops a mathematical model in the form of mixed integer linear programming and compares it with the available model in the literature. The proposed model outperforms the available model in terms of both size complexity and computational complexity. Then, an effective metaheuristic algorithm based on iterated local search is proposed and compared with a tabu search and variable neighbourhood search algorithms proposed previously for the same problem. A complete experiment is conducted to evaluate the algorithms for performance. All the results show the superiority of the proposed algorithm against the available ones.     

Real-time deadlock-free scheduling for semiconductor track systems based on colored timed Petri nets

This paper addresses the problem of real-time deadlock-free scheduling for a semiconductor track system. The system is required to process wafers continuously, cassette by cassette. The process is not necessarily a repeated one. In addition, the system is deadlock-prone and its modules are failure-prone. Thus, real-time scheduling approaches are required to achieve high-performance. The problem can be solved in a hierarchical way. A deadlock avoidance policy is developed for the system as a lower-layer controller. With the support of the deadlock avoidance policy, heuristic rules are proposed to schedule the system in real-time. An effective modeling tool, colored–timed resource-oriented Petri net, is presented. It is shown that with this model we can schedule a system to achieve satisfactory results in real-time. This method is tolerant to module failures.     

A coloured Petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles

To achieve a significant improvement in the overall performance of a flexible manufacturing system, the scheduling process must consider the interdependencies that exist between the machining and transport systems. However, most works have addressed the scheduling problem as two independent decision making problems, assuming sufficient capacity in the transport system. In this paper, we study the simultaneous scheduling (SS) problem of machines and automated guided vehicles using a timed coloured Petri net (TCPN) approach under two performance objectives; makespan and exit time of the last job. The modelling approach allows the evaluation of all the feasible vehicle assignments as opposed to the traditional dispatching rules and demonstrates the benefits of vehicle-controlled assignments over machine-controlled for certain production scenarios. In contrast with the hierarchical decomposition technique of existing approaches, TCPN is capable of describing the dynamics and evaluating the performance of the SS problem in a single model. Based on TCPN modelling, SS is performed using a hybrid heuristic search algorithm to find optimal or near-optimal schedules by searching through the reachability graph of the TCPN with heuristic functions. Large-sized instances are solved in relatively short computation times, which were a priori unsolvable with conventional search algorithms. The algorithm’s performance is evaluated on a benchmark of 82 test problems. Experimental results indicate that the proposed algorithm performs better than the conventional ones and compares favourably with other approaches.     

Dynamic production control in a serial line with process queue time constraint

This research examines the production control problem in two-station tandem queueing systems under time constraints. In these two-station tandem queueing systems, jobs must first be processed at the upstream station and then the downstream station. For each job, the sum of the waiting and processing time in the downstream queue is limited by an upper bound. This time constraint is called the process queue time constraint. When the process queue time constraint is violated, a significant scrap cost will be accrued. In this research, we develop a Markov decision model to study the production control problem under process queue time constraints. The objective is to minimise the sum of the expected long-run average inventory holding costs and scrap costs. According to the Markov decision model, an interesting exhaustive structure of the optimal production control policy is found. Based on this exhaustive structure, an efficient algorithm is developed to solve the production control problem numerically. The performance of the proposed algorithm is verified by a simulation study. Compared with other heuristics in the literature, the proposed algorithm can significantly reduce production costs while improving system throughput and utilisation.