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.     

A hybrid differential evolution algorithm for a two-stage flow shop on batch processing machines with arbitrary release times and blocking

Batch processing machines (BPMs) have important applications in a variety of industrial systems. This paper considers the problem of scheduling two BPMs in a flow shop with arbitrary release times and blocking such that the makespan is minimised. The problem is formulated as a mixed integer programming model. Subsequently, a hybrid discrete differential evolution (HDDE) algorithm is proposed. In the algorithm, individuals in the population are first represented as discrete job sequences, and mutation and crossover operators are applied based on the representation. Second, after using the first-fit rule to form batches, a novel least idle/blocking time heuristic is developed to schedule the batches in the flow shop. Furthermore, an effective local search technique is embedded in the algorithm to enhance the exploitation ability. The performance of the proposed algorithm is evaluated by comparing its results to a commercial solver (CPLEX), a genetic algorithm and a simulated annealing algorithm. Computational experiments demonstrate the superiority of the HDDE algorithm in terms of solution quality, robustness and run time.     

A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles

In this paper we address the problem of simultaneous scheduling of machines and vehicles in flexible manufacturing systems. The studied problem is a job shop where the jobs have to be transported between the machines by automatic guided vehicles. In addition to the processing of jobs, we consider the transportation aspect as an integral part of the optimization process. To deal with this problem, we propose a new solution representation based on vehicles rather than machines. Each solution can thus be evaluated using a discrete event approach. An efficient neighbouring system is then described and implemented into three different metaheuristics: iterated local search, simulated annealing and their hybridisation. Computational results are presented for a benchmark of 40 literature instances. New upper bounds are found for 11 of them, showing the effectiveness of the presented approach.     

A relative position-coded differential evolution for loop-based station sequencing problem

Loop layout is very common in flexible manufacturing systems. The quality of the layout scheme directly affects productivity of flexible manufacturing systems. The loop-based station sequencing problem (LSSP) that determines the arrangement of the facilities around a closed loop belongs to the category of the combinatorial optimisation problem, which is known to be NP-Hard. Therefore, the heuristic and meta-heuristic methods are generally adopted to solve the LSSP. In order to improve the existing methods, this paper takes into consideration the permutation property of the LSSP, and proposes an integer-coded differential evolution (DE) algorithm, named as relative position-coded DE. Compared with existing real-coded DEs, the proposed algorithm possesses the following favourable characteristics: (1) it does not need mapping from floating point vectors to integer sequence; (2) the coding space of the new algorithm corresponds with the solution space of LSSP; (3) it avoids the illegal chromosomes in the solving process. Experimental results showed that the proposed relative position-coded DE outperforms the existing DEs, GA, PSO, and SA, especially in the case of large-scale LSSP.     

A discrete artificial bee colony algorithm incorporating differential evolution for the flow-shop scheduling problem with blocking

A flow-shop scheduling problem with blocking has important applications in a variety of industrial systems but is underrepresented in the research literature. In this study, a novel discrete artificial bee colony (ABC) algorithm is presented to solve the above scheduling problem with a makespan criterion by incorporating the ABC with differential evolution (DE). The proposed algorithm (DE-ABC) contains three key operators. One is related to the employed bee operator (i.e. adopting mutation and crossover operators of discrete DE to generate solutions with good quality); the second is concerned with the onlooker bee operator, which modifies the selected solutions using insert or swap operators based on the self-adaptive strategy; and the last is for the local search, that is, the insert-neighbourhood-based local search with a small probability is adopted to improve the algorithm's capability in exploitation. The performance of the proposed DE-ABC algorithm is empirically evaluated by applying it to well-known benchmark problems. The experimental results show that the proposed algorithm is superior to the compared algorithms in minimizing the makespan criterion.     

One‐sided control chart based on support vector machines with differential evolution algorithm

The statistical learning classification techniques have been successfully applied to statistical process control problems. In this paper, we proposed a one‐sided control chart based on support vector machines (SVMs) and differential evolution (DE) algorithm to monitor a process with multivariate quality characteristics. The SVM classifier provides a continuous distance from the boundary, and the DE algorithm is used to obtain the optimal parameters of the SVM model by minimizing mean absolute error (MAE). The average run length of the proposed chart is computed using the Monte Carlo simulation approach. Several simulated cases are conducted using a multivariate normal distribution with 10 and 20 dimensions and three different process shift scenarios. In addition, we consider two non‐normal distribution cases. The ARL performance of the proposed chart is better than the distance‐based SVM chart. A real example is used to illustrate the application of the proposed control chart.     

Minimizing makespan in a no-wait flowshop with two batch processing machines using estimation of distribution algorithm

This paper studies the problem of minimising makespan in a no-wait flowshop with two batch processing machines (comprised of a parallel batch processing machine and a serial batch processing machine), non-identical job sizes and unequal ready times. We propose a population-based evolutionary method named estimation of distribution algorithm (EDA). Firstly, the individuals in the population are coded into job sequences. Then, a probabilistic model is built to generate new population and an incremental learning method is developed to update the probabilistic model. Thirdly, the best-fit heuristic is used to group jobs into batches and a least idle/waiting time approach is proposed to sequence the batches on batch processing machines. In addition, some problem-dependent local search heuristics are incorporated into the EDA to further improve the searching quality. Computational simulation and comparisons with some existing algorithms demonstrate the effectiveness and robustness of the proposed algorithm. Furthermore, the effectiveness of embedding the local search method in the EDA is also evaluated.     

A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan

In this paper, we present a branch and bound algorithm for the parallel batch scheduling of jobs having different processing times, release dates and unit sizes. There are identical machines with a fixed capacity and the number of jobs in a batch cannot exceed the machine capacity. All batched jobs are processed together and the processing time of a batch is given by the greatest processing time of jobs in that batch. We compare our method to a mixed integer program as well as a method from the literature that is capable of optimally solving instances with a single machine. Computational experiments show that our method is much more efficient than the other two methods in terms of solution time for finding the optimal solution.     

Scheduling vehicles in automated transportation systems Algorithms and case study

One of the major planning issues in large scale automated transportation systems is so-called empty vehicle management, the timely supply of vehicles to terminals in order to reduce cargo waiting times. Motivated by a Dutch pilot project on an underground cargo transportation system using Automated Guided Vehicles (AGVs), we developed several rules and algorithms for empty vehicle management, varying from trivial First-Come, First-Served (FCFS) via look-ahead rules to integral planning. For our application, we focus on attaining customer service levels in the presence of varying order priorities, taking into account resource capacities and the relation to other planning decisions, such as terminal management. We show how the various rules are embedded in a framework for logistics control of automated transportation networks. Using simulation, the planning options are evaluated on their performance in terms of customer service levels, AGV requirements and empty travel distances. Based on our experiments, we conclude that look-ahead rules have significant advantages above FCFS. A more advanced so-called serial scheduling method outperforms the look-ahead rules if the peak demand quickly moves amongst routes in the system. Received: June 21, 2000 / Accepted: January 22, 2001     

Reliability reallocation for cost uncertainty of fuel cell vehicles via improved differential evolution algorithm

A fuel cell vehicle (FCV) is composed of many subsystems; it is necessary to reallocate subsystem reliability to improve FCV system reliability. A comprehensive evaluation method considering uncertainty is proposed to obtain the interval value of feasibility factor. The FCV cost uncertainty model is established on the basic of parameters such as feasibility factor, initial reliability, limit reliability, and subsystem cost. To solve the optimization problem for cost uncertainty, the cost interval model is transformed into a deterministic model by interval order relation. An improved differential evolution (DE) algorithm is proposed to reallocate subsystem reliability for minimum cost.     

Scheduling with controllable processing times and compression costs using population-based heuristics

This paper considers the single machine scheduling problem of jobs with controllable processing times and compression costs and the objective to minimise the total weighted job completion time plus the cost of compression. The problem is known to be intractable, and therefore it was decided to be tackled by population-based heuristics namely differential evolution (DE), particle swarm optimisation (PSO), genetic algorithms (GAs), and evolution strategies (ES). Population-based heuristics have found wide application in most areas of production research including scheduling theory. It is therefore surprising that this problem has not yet received any attention from the corresponding heuristic algorithms community. This work aims at contributing to fill this gap. An appropriate problem representation scheme is developed together with a multi-objective procedure to quantify the trade-off between the total weighted job completion time and the cost of compression. The four heuristics are evaluated and compared over a large set of test instances ranging from five to 200 jobs. The experiments showed that a differential evolution algorithm is superior (with regard to the quality of the solutions obtained) and faster (with regard to the speed of convergence) to the other approaches.     

Solving steel coil ship stowage-planning problem using hybrid differential evolution

As an important optimisation problem in the finished product terminal of an iron and steel enterprise, the steel coil ship stowage-planning problem is to determine the stowing locations for the planned coils on a ship. Although the problem has attracted attention, the research has focused only on the optimisation for the ship. In this study, the problem is investigated from the view of improving operation efficiency of the cranes on the quay and in the warehouse. For this purpose, an integer-programming model is established to minimise the coil dispersion on the ship and the moving distance of the warehouse cranes by determining the stowing locations and loading sequence of the coils. To improve the solution efficiency, a two-level hybrid differential evolution (TLDE) composed of a continuous DE and a discrete DE is designed to assign the coils to the rows on the ship, and then allocate locations for them. Further, a subpopulation-based local search and a human experience-based heuristic are developed to further adjust the coils within each row and to produce initial population for TLDE, respectively. Extensive comparison experiments are performed to demonstrate the proposed algorithm. Numerical results confirm that TLDE is an efficient method for solving the SSPP.     

A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles

In this paper, the problem of simultaneous scheduling of machines and identical automated guided vehicles (AGVs) in flexible manufacturing systems is addressed with the objective of minimizing the makespan. This problem is composed of two interrelated decision problems: the scheduling of machines, and the scheduling of AGVs. Both problems are known to be NP-complete, resulting in a more complicated NP-complete problem when they are considered simultaneously. A new hybrid Genetic-algorithm/heuristic coding scheme is developed for the studied problem. The developed coding scheme is combined with a set of genetic algorithm (GA) operators selected from the literature of the applications of GAs to the scheduling problems. The algorithm is applied to a set of 82 test problems, which was constructed by other researchers, and the comparison of the results indicates the superior performance of the developed coding.     

Scheduling of deadlock and failure-prone automated manufacturing systems via hybrid heuristic search

This work focuses on the scheduling problem of deadlock and failure-prone automated manufacturing systems, and presents a new scheduling method by combining a robust supervisory control policy and hybrid heuristic search. It aims to minimise makespan, i.e. the completion time of the last part. Based on the extended reach ability graph of the system, it establishes a new heuristic function and two dispatching rules to guide the search process for a schedule. By embedding a robust supervisory control policy into the search process, it develops a polynomial robust dynamic window search algorithm. Failure and repair events of unreliable resources may occur during the execution of a schedule obtained by the proposed algorithm and may make the schedule infeasible. To reduce the influence caused by them and ensure all parts to be finished, this work proposes two event-driven strategies. The first one suspends the execution of the parts requiring failed resources and those to be started until all failed resources are repaired and permits only those parts that have already been processed on working machines to be completed. The second one invokes the proposed algorithm to obtain a new schedule at the vertex generated after a resource failure or repair event and executes the new schedule. Both strategies are effective while the latter performs better at the expense of more computation.     

A hybrid differential evolution and estimation of distribution algorithm based on neighbourhood search for job shop scheduling problems

Job shop scheduling problem (JSSP) is a typical NP-hard problem. In order to improve the solving efficiency for JSSP, a hybrid differential evolution and estimation of distribution algorithm based on neighbourhood search is proposed in this paper, which combines the merits of Estimation of distribution algorithm and Differential evolution (DE). Meanwhile, to strengthen the searching ability of the proposed algorithm, a chaotic strategy is introduced to update the parameters of DE. Two mutation operators are adopted. A neighbourhood search (NS) algorithm based on blocks on critical path is used to further improve the solution quality. Finally, the parametric sensitivity of the proposed algorithm has been analysed based on the Taguchi method of design of experiment. The proposed algorithm was tested through a set of typical benchmark problems of JSSP. The results demonstrated the effectiveness of the proposed algorithm for solving JSSP.     

集装箱码头岸吊作业调度建模及调度策略研究

岸吊作业调度对集装箱码头整体运营效率具有重要影响.综合考虑岸吊实际作业中的特有约束,包括预定义顺序约束、依赖于作业次序的设备调整时间、岸吊干涉约束,建立岸吊作业调度问题的混合整数规划模型.针对混合装卸模式,使用启发式算法生成预定义作业顺序,在此基础上采用基于连续贝作业策略的启发式算法对问题进行求解.数据实验结果显示基于SPT规则和连续贝作业的启发式算法能有效利用混合装卸带来的时间节省,减少设备调整时间,对实际岸吊作业调度具有指导意义.     

Electric arc modeling of the EAF using differential evolution algorithm

?tore Steel Ltd. makes more than 1400 steel grades. The highest costs in steel production from scrap stems from the electric arc furnace electric energy consumption. Electrical energy is used to produce heat energy generated by the burning arc between the graphite electrodes and steel scrap. In general, the balanced heat input of all electrodes is essential. Based on the input of thermal energy from all electrodes, also the possibility of occurrence of hot and cold spots in the electric arc furnace can be determined. Perception of and the elimination of the unequal heat load of electrodes have a major impact on reducing operating costs and increasing the efficiency of the electric arc furnace production. Most authors have modeled the arc furnace as an electrical equivalent circuit, where the electric arc is modeled using the macroscopic approach. In this paper, the microscopic approach to the electric arc model is described, where a set of equations (electrical neutrality, Dalton law, Saha–Eggert) was solved using differential evolution algorithm. The results of modeling were practically confirmed by measuring electric parameters (voltage, current, active power) during the electric arc furnace operation. In November 2016, the investment in a new electrode controller using implemented logic will be carried out.     

Minimising total weighted earliness and tardiness penalties on identical parallel machines using a fast ruin-and-recreate algorithm

This paper studies the scheduling problem of minimising total weighted earliness and tardiness penalties on identical parallel machines against a restrictive common due date. This problem is NP-hard in the strong sense and arises in many just-in-time production environments. A fast ruin-and-recreate (FR&R) algorithm is proposed to obtain high-quality solutions to this complex problem. The proposed FR&R algorithm is tested on a well-known set of benchmark test problems that are taken from the literature. Computational results provide evidence of the efficiency of FR&R, which consistently outperform existing algorithms when applied to benchmark instances. This work provides a viable alternative approach for efficiently solving this practical but complex scheduling problem.     

An efficient hybrid evolutionary heuristic using genetic algorithm and simulated annealing algorithm to solve machine loading problem in FMS

In this paper, a machine loading problem in a flexible manufacturing system (FMS) is discussed, with bi-criterion objectives of minimising system imbalance and maximising system throughput in the occurrence of technological constraints such as available machining time and tool slots. A mathematical model is used to select machines, assign operations and the required tools in order to minimise the system's imbalance while maximising the throughput. An efficient evolutionary algorithm by hybridising the genetic algorithm (GA) and simulated annealing (SA) algorithm called GASA is proposed in this paper. The performance of the GASA is tested by using 10 sample dataset and the results are compared with the heuristics reported in the literature. The influence of genetic operators on the evolutionary search in GASA is studied and reported. Two machine selection heuristics are proposed and their influence on the quality of the solution is also studied. Extensive computational experiments have been carried out to evaluate the performance of the proposed evolutionary heuristics and the results are presented in tables and figures. The results clearly support the better performance of GASA over the algorithms reported in the literature.     

Scheduling policies in multi-product manufacturing systems with sequence-dependent setup times and finite buffers

Multi-product production systems with sequence-dependent setup times are typical in the manufacturing of semiconductor chips and other electronic products. In such systems, the scheduling policies coordinating the production of multiple product types play an important role. In this paper, we study a multi-product manufacturing system with finite buffers, sequence-dependent setup times and various scheduling policies. Using continuous-time Markov chain models, we evaluate the performance of such systems under seven scheduling policies, i.e. cyclic, shortest queue, shortest processing time, shortest overall time (including setup time and processing time), longest queue, longest processing time, and longest overall time. The impacts of these policies on system throughput are compared, and the conditions characterising the superiority of each policy are investigated. The results of this work can provide production engineers and supervisors practical guidance to operate multi-product manufacturing systems with sequence-dependent setups.