Search

As a new swarm intelligence algorithm, sparrow search algorithm (SSA) has the advantages of fewer parameters, simplicity, strong global and local search capability, and has been successfully applied in continuous problem and its engineering applications. Meanwhile, SSA for job shop scheduling problem (JSP) is studied rarely and would arise new problems such as conversion from continuous space to discrete space, falling into local optimum, etc. To address these issues, considering the features of SSA and JSP, the multi-strategy improved sparrow search algorithm (MISSA) is devised to solve minimum makespan of JSP. First, the operation sort based encoding transformation method of SSA for discrete problems is devised. Second, tent chaotic mapping is instead of random generation to initialize sparrow population to expand space of solution. Third, the crossover operation of genetic algorithm is introduced in producers and scroungers positions updating to maintain the population diversity and improve the algorithm search ability. Fourth, the mutation operation of genetic algorithm is adopted in the position update of the vigilance to enhance the local searching capability. Fifth, the simulated annealing algorithm was adopted to avoid the local optimal solution and reach the global best solution. In the end, using 10 classical examples of JSP and one practical scheduling example, comparisons of MISSA with other algorithms are simulated, and the results show that MISSA effectively solves JSP. [ABSTRACT FROM AUTHOR]

Flexible job-shop scheduling is considerably important in the modern intelligent manufacturing factory. In a real job shop, transportation and setup times account for a large percentage of the total processing flow, and with today's companies demanding higher delivery times, the feasibility and punctuality of scheduling will be considerably reduced if these time constraints are ignored. Recently, several companies have become green in their manufacturing processes. However, transportation, setup, and delivery times have rarely been combined with energy efficiency. To solve this problem, we employed an integer programming approach to develop a complete mathematical model of the problem and simultaneously optimized four objectives: maximum completion time, total energy consumption, workload of critical machines, and penalties for earliness/tardiness. Subsequently, an evolutionary algorithm incorporating reinforcement learning was proposed to solve the model. The algorithm had the following features: (1) four initialization strategies were designed to obtain high-quality populations; (2) a reinforcement learning-based parameter-adaptive strategy was proposed to guide the population to select the best parameters; (3) a critical path-based neighborhood structure with transportation and setup times was designed, and according to the objectives of this study, four additional neighborhood structures were designed; (4) a reference point-based non-dominated sorting selection was presented to guide the solution toward the Pareto-optimal front; and (5) an external archive was proposed to enhance the utilization of abandoned historical solutions. Finally, the effectiveness of this algorithm was demonstrated using 33 benchmark instances of variants and comparison experiments. [ABSTRACT FROM AUTHOR]

In the practical production, the transportation of jobs is existed between different machines. These transportation operations directly affect the production cycle and the production efficiency. In this study, an improved memetic algorithm is proposed to solve the flexible job shop scheduling problem with transportation times, and the optimization objective is minimizing the makespan. In the improved memetic algorithm, an effective simulated annealing algorithm is adopted in the local search process, which combines the elite library and mutation operation. All the feasible solutions are divided into general solutions and local optimal solutions according to the elite library. The general solutions are executed by the simulated annealing algorithm to improve the quality, and the local optimal solutions are executed by the mutation operation to increase the diversity of the solution set. Comparison experiments with the improved genetic algorithm show that the improved memetic algorithm has better search performance and stability. [ABSTRACT FROM AUTHOR]

In the practical production, the transportation of jobs is existed between different machines. These transportation operations directly affect the production cycle and the production efficiency. In this study, an improved memetic algorithm is proposed to solve the flexible job shop scheduling problem with transportation times, and the optimization objective is minimizing the makespan. In the improved memetic algorithm, an effective simulated annealing algorithm is adopted in the local search process, which combines the elite library and mutation operation. All the feasible solutions are divided into general solutions and local optimal solutions according to the elite library. The general solutions are executed by the simulated annealing algorithm to improve the quality, and the local optimal solutions are executed by the mutation operation to increase the diversity of the solution set. Comparison experiments with the improved genetic algorithm show that the improved memetic algorithm has better search performance and stability. [ABSTRACT FROM AUTHOR]

Production scheduling problems are typically combinational optimization problems named bases on the processing routes of jobs on different machines. In this paper, the flexible job shop scheduling problem aimed to minimize the maximum completion times of operations or makespan is considered. To solve such an NP-hard problem, variable neighborhood search (VNS) based on genetic algorithm is proposed to enhance the search ability and to balance the intensification and diversification. VNS algorithm has shown excellent capability of local search with systematic neighborhood search structures. External library is improved to save the optimal or near optimal solutions during the iterative process, and when the objective value of the optimal solutions are the same, the scheduling Gantt charts need to be considered. To evaluate the performance of our proposed algorithm, benchmark instances in different sizes are optimized. Consequently, the computational results and comparisons illustrate that the proposed algorithm is efficiency and effectiveness. [ABSTRACT FROM AUTHOR]

The dynamic rescheduling problem in flexible manufacturing systems (FMS) has historically emphasized the schedule efficiency. However, energy consumption is a basic need for different purposes in manufacturing systems around the world. This paper proposes an innovative approach to study the dynamic scheduling problem in FMS, taking the objectives of minimum or maximum energy consumption into account. A new goal programming mathematical model, which considers the energy consumption and the schedule efficiency simultaneously, is presented for solving this problem. A rescheduling method based on the genetic algorithm is introduced to address the dynamic rescheduling problem in FMS. A period policy is selected to deal with the dynamic feature of the problem. Numerical experiments have been designed to test and evaluate the performance of the proposed model. The experimental results show that the minimum energy consumption model can save the energy consumption and enhance the schedule efficiency. [ABSTRACT FROM AUTHOR]

• Dynamic flexible job shop scheduling problem with machine breakdown is studied. • A two-stage algorithm based on convolutional neural network is proposed. • The improved imperialist competition algorithm is proposed to generate schedules. • A predictive model is proposed to predict the robustness of scheduling. In the actual manufacturing process, the environment of the job shop is complex. There will be many kinds of uncertainties such as random job arrivals, machine breakdowns, order cancellations and other dynamic events. In this paper, an effective two-stage algorithm based on convolutional neural network is proposed to solve the flexible job shop scheduling problem (FJSP) with machine breakdown. A bi-objective dynamic flexible job shop scheduling problem (DFJSP) model with the objective of maximum completion time and robustness is established. In the two-stage algorithm, the first stage is to train the prediction model by convolutional neural network (CNN). The second stage is to predict the robustness of scheduling through the model trained in the first stage. First, an improved imperialist competition algorithm (ICA) is proposed to generate training data. Then, a predictive model constructed by CNN was proposed, and an alternative metric called RMn was developed to evaluate robustness. RMn evaluates that the float time has an effect on the robustness through the information of machine breakdown, workload and float time of the operation. The experimental results show that the proposed two-stage algorithm is effective for solving DFJSP, and RMn can evaluate the robustness of scheduling more quickly, efficiently and accurately. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we proposed an effective genetic algorithm for solving the flexible job-shop scheduling problem (FJSP) to minimize makespan time. In the proposed algorithm, Global Selection (GS) and Local Selection (LS) are designed to generate high-quality initial population in the initialization stage. An improved chromosome representation is used to conveniently represent a solution of the FJSP, and different strategies for crossover and mutation operator are adopted. Various benchmark data taken from literature are tested. Computational results prove the proposed genetic algorithm effective and efficient for solving flexible job-shop scheduling problem. [ABSTRACT FROM AUTHOR]

The flexible job shop scheduling problem is a very important problem in factory scheduling. Most of existing researches only consider the processing time of each operation, however, jobs often require transporting to another machine for the next operation while machines often require setup to process the next job. In addition, the times associated with these steps increase the complexity of this problem. In this paper, the flexible job scheduling problem is solved that incorporates not only processing time but setup time and transportation time as well. After presenting the problem, an improved genetic algorithm is proposed to solve the problem, with the aim of minimizing the makespan time, minimizing total setup time, and minimizing total transportation time. In the improved genetic algorithm, initial solutions are generated through three different methods to improve the quality and diversity of the initial population. Then, a crossover method with artificial pairing is adopted to preserve good solutions and improve poor solutions effectively. In addition, an adaptive weight mechanism is applied to alter mutation probability and search ranges dynamically for individuals in the population. By a series of experiments with standard datasets, we demonstrate the validity of our approach and its strong performance. [ABSTRACT FROM AUTHOR]

The original version of this article unfortunately contained a mistake in the acknowledgement statement. It should read as follow "This paper presents work funded by the National Natural Science Foundation of China (No. 61203179), Excellent Youth Foundation of Science & Technology Innovation of Henan Province (No. 184100510001), and Key scientific research projects of Henan Province (No. 182102210457). Also, we would like to thank the Collaborative Innovation Center for Aviation Economy Development of Henan Province.". The oricd of the corresponding author is revised to http://orcid.org/0000-0001-9143-2922. Also the e-mail of the corresponding author is revised to zgh_hust@qq.com. [ABSTRACT FROM AUTHOR]