A hybrid differential evolution algorithm for job shop scheduling problems with expected total tardiness criterion

In real-world manufacturing systems, the processing of jobs is frequently affected by various unpredictable events. However, compared with the extensive research for the deterministic model, study on the random factors in job shop scheduling has not received sufficient attention. In this paper, we propose a hybrid differential evolution (DE) algorithm for the job shop scheduling problem with random processing times under the objective of minimizing the expected total tardiness (a measure for service quality). First, we propose a performance estimate for roughly comparing the quality of candidate solutions. Then, a parameter perturbation algorithm is applied as a local search module for accelerating the convergence of DE. Finally, the K-armed bandit model is utilized for reducing the computational burden in the exact evaluation of solutions based on simulation. The computational results on different-scale test problems validate the effectiveness and efficiency of the proposed approach.     

A hybrid immune simulated annealing algorithm for the job shop scheduling problem

A hybrid simulated annealing algorithm based on a novel immune mechanism is proposed for the job shop scheduling problem with the objective of minimizing total weighted tardiness. The proposed immune procedure is built on the following fundamental idea: the bottleneck jobs existing in each scheduling instance generally constitute the key factors in the attempt to improve the quality of final schedules, and thus, the sequencing of these jobs needs more intensive optimization. To quantitatively describe the bottleneck job distribution, we design a fuzzy inference system for evaluating the bottleneck level (i.e. the criticality) of each job. By combining the immune procedure with a simulated annealing algorithm, we design a hybrid optimization algorithm which is subsequently tested on a number of job shop instances. Computational results for different-sized instances show that the proposed hybrid algorithm performs effectively and converges fast to satisfactory solutions.     

A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardinessobjective

In modern manufacturing systems, due date related performance is becoming increasingly important in maintaining a high service reputation. However, compared with the extensive research on makespan minimization, research on the total weighted tardiness objective is comparatively scarce, partly because this objective function is more difficult and complex to optimize. In this paper, we focus on the job shop scheduling problem with the objective of minimizing total weighted tardiness. First, we discuss the mathematical programming model and its duality when the processing orders for each machine are fixed. Then, a block-based neighborhood structure is defined and its important properties are shown. Finally, a simulated annealing algorithm is designed which directly utilizes the features of this neighborhood. According to the computational results, the new neighborhood considerably promotes the searching capability of simulated annealing and helps it converge to high-quality solutions.     

A heuristic for job shop scheduling to minimize total weighted tardiness

This paper considers the job shop scheduling problem to minimize the total weighted tardiness with job-specific due dates and delay penalties, and a heuristic algorithm based on the tree search procedure is developed for solving the problem. A certain job shop scheduling to minimize the maximum tardiness subject to fixed sub-schedules is solved at each node of the search tree, and the successor nodes are generated, where the sub-schedules of the operations are fixed. Thus, a schedule is obtained at each node, and the sub-optimum solution is determined among the obtained schedules. Computational results on some 10 jobs and 10 machines problems and 15 jobs and 15 machines problems show that the proposed algorithm can find the sub-optimum solutions with a little computation time.     

Accelerated simulated annealing algorithm applied to the flexible job shop scheduling problem

This paper presents a simulated annealing algorithm accelerated by a partial scheduling mechanism and a cooling schedule mechanism that is a function of the standard deviation. This facilitates a rapid approach to good solutions in the flexible job shop scheduling problem (FJSSP). The results demonstrate that for benchmark instances of several sizes, simulated annealing that implements the proposed mechanism converges more quickly to good solutions than simulated annealing that does not implement the proposed mechanism.     

Neighbourhood generation mechanism applied in simulated annealing to job shop scheduling problems

This paper presents a neighbourhood generation mechanism for the job shop scheduling problems (JSSPs). In order to obtain a feasible neighbour with the generation mechanism, it is only necessary to generate a permutation of an adjacent pair of operations in a scheduling of the JSSP. If there is no slack time between the adjacent pair of operations that is permuted, then it is proven, through theory and experimentation, that the new neighbour (schedule) generated is feasible. It is demonstrated that the neighbourhood generation mechanism is very efficient and effective in a simulated annealing.     

A hybrid genetic algorithm for the job shop scheduling problems

The Job Shop Scheduling Problem (JSSP) is one of the most general and difficult of all traditional scheduling problems. The goal of this research is to develop an efficient scheduling method based on genetic algorithm to address JSSP. We design a scheduling method based on Single Genetic Algorithm (SGA) and Parallel Genetic Algorithm (PGA). In the scheduling method, the representation, which encodes the job number, is made to be always feasible, the initial population is generated through integrating representation and G&T algorithm, the new genetic operators and selection method are designed to better transmit the temporal relationships in the chromosome, and island model PGA are proposed. The scheduling methods based on genetic algorithm are tested on five standard benchmark JSSP. The results are compared with other proposed approaches. Compared to traditional genetic algorithm, the proposed approach yields significant improvement in solution quality. The superior results indicate the successful incorporation of a method to generate initial population into the genetic operators.     

Discrete hybrid cuckoo search and simulated annealing algorithm for solving the job shop scheduling problem

The Journal of Supercomputing - The job shop scheduling problem (JSSP) is a popular NP-hard scheduling problem that simulates the scheduling problems of different real-world applications in fields...     

A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts

This paper addresses the problem of scheduling parts in job shop cellular manufacturing systems by considering exceptional parts that need to visit machines in different cells and reentrant parts which need to visit some machines more than once in non-consecutive manner. Initially, an integer linear programming (ILP) model is presented for the problem to minimize the makespan, which considers intercellular moves and non-consecutive multiple processing of parts on a machine. Due to the complexity of the model, a simulated annealing (SA) based solution approach is developed to solve the problem. To increase the efficiency of the search algorithm, a neighborhood structure based on the concept of blocks is applied. Subsequently, the efficiency of the ILP model and the performance of the proposed SA are assessed over a set of problem instances taken from the literature. The proposed ILP model was coded in Lingo 8.0 and the solution obtained by the proposed SA was compared to the optimal values. The computational results demonstrate that the proposed ILP model and SA algorithm are effective and efficient for this problem.     

一种求解双目标job shop问题的混合进化算法

提出一种求解双目标job shop排序问题的混合进化算法．该算法采用改进的精英复制策略,降低了计算复杂性;通过引入递进进化模式,避免了算法的早熟;通过递进过程中的非劣解邻域搜索,增强了算法局部搜索性能．采用该算法和代表性算法NSGA-Ⅱ,MOGLS对82个标准双目标job shop算例进行优化对比,所得结果验证了该算法求解双目标job shop排序问题的有效性．     

A two-stage genetic algorithm for multi-objective job shop scheduling problems

This paper presents a two-stage genetic algorithm (2S-GA) for multi-objective Job Shop scheduling problems. The 2S-GA is proposed with three criteria: Minimize makespan, Minimize total weighted earliness, and Minimize total weighted tardiness. The proposed algorithm is composed of two Stages: Stage 1 applies parallel GA to find the best solution of each individual objective function with migration among populations. In Stage 2 the populations are combined. The evolution process of Stage 2 is based on Steady-State GA using the weighted aggregating objective function. The algorithm developed can be used with one or two objectives without modification. The genetic algorithm is designed and implemented with the GALIB object library. The random keys representation is applied to the problem. The schedules are constructed using a permutation with m-repetitions of job numbers. Performance of the proposed algorithm is tested on published benchmark instances and compared with results from other published approaches for both the single objective and multi-objective cases. The experimental results show that 2S-GA is effective and efficient to solve job shop scheduling problem in term of solution quality.     

A hybrid genetic algorithm for no-wait job shop scheduling problems

A no-wait job shop (NWJS) describes a situation where every job has its own processing sequence with the constraint that no waiting time is allowed between operations within any job. A NWJS problem with the objective of minimizing total completion time is a NP-hard problem and this paper proposes a hybrid genetic algorithm (HGA) to solve this complex problem. A genetic operation is defined by cutting out a section of genes from a chromosome and treated as a subproblem. This subproblem is then transformed into an asymmetric traveling salesman problem (ATSP) and solved with a heuristic algorithm. Subsequently, this section with new sequence is put back to replace the original section of chromosome. The incorporation of this problem-specific genetic operator is responsible for the hybrid adjective. By doing so, the course of the search of the proposed genetic algorithm is set to more profitable regions in the solution space. The experimental results show that this hybrid genetic algorithm can accelerate the convergence and improve solution quality as well.     

A hybridization of simulated annealing and electromagnetic-like mechanism for job shop problems with machine availability and sequence-dependent setup times to minimize total weighted tardiness

In this paper, we explore job shop problems with two recently popular and realistic assumptions, sequence-dependent setup times and machine availability constraints to actualize the problem. The criterion is a minimization of total weighted tardiness. We establish a simple criterion to integrate machine availability constraints and scheduling decisions simultaneously. We propose a hybrid meta-heuristic to tackle the given problem. This meta-heuristic method, called EMSA, is a combination of two meta-heuristics: (1) Electromagnetic-like mechanism (EM); and (2) simulated annealing (SA). The hybridization is done to overcome some existing drawbacks of each of these two algorithms. To evaluate the proposed hybrid meta-heuristic method, we carry out a benchmark by which the proposed EMSA is compared with some existing algorithms as well as simulated annealing and electromagnetic-like mechanism alone in a fixed given computational time. All the related results and analysis obtained through the benchmark illustrate that our proposed EMSA is very effective and supersedes the foregoing algorithms.     

Fast simulated annealing hybridized with quenching for solving job shop scheduling problem

Various heuristic based methods are available in literature for optimally solving job shop scheduling problems (JSSP). In this research work a novel approach is proposed which hybridizes fast simulated annealing (FSA) with quenching. The proposed algorithm uses FSA for global search and quenching for localized search in neighborhood of current solution, while tabu list is used to restrict search from revisiting previously explored solutions. FSA is started with a relatively higher temperature and as search progresses temperature is gradually reduced to a value close to zero. The overall best solution (BS) is maintained throughout execution of the algorithm. If no improvement is observed in BS for certain number of iterations then quenching cycle is invoked. During quenching cycle current temperature is reduced to nearly freezing point and iterations are increased by many folds, as a result of this change search becomes nearly greedy. The strength of the proposed algorithm is that even in quenching mode escape from local optima is possible due to use of Cauchy probability distribution and non-zero temperature. At the completion of quenching cycle previous values of search parameters are restored and FSA takes over, which moves search into another region of solution space. Effectiveness of proposed algorithm is established by solving 88 well known benchmark problems taken form published work. The proposed algorithm was able to solve 45 problems optimally to their respective best known values in reasonable time. The proposed algorithm has been compared with 18 other published works. The experimental results show that the proposed algorithm is efficient in finding solution to JSSP.     

Electromagnetism-like mechanism and simulated annealing algorithms for flowshop scheduling problems minimizing the total weighted tardiness and makespan

This paper presents an efficient meta-heuristic algorithm based on electromagnetism-like mechanism (EM), in which has been successfully implemented in a few combinatorial problems. We propose the EM for scheduling the flow shop problem that minimizes the makespan and total weighted tardiness and considers transportation times between machines and stage skipping (i.e., some jobs may not need to be processed on all the machines). To show the efficiency of this proposed algorithm, we also apply simulated annealing (SA) and some other well-recognized constructive heuristics, such as SPT, NEH, (g/2, g/2) Johnson’ rule, EWDD, SLACK, and NEH_EWDD for the given problems. To evaluate the performance and robustness of our proposed EM, we experiment a number of test problems. Our computational results show that our proposed EM in almost all cases outperforms SA and other foregoing heuristics applied to this paper.     

A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective

In this paper we consider the job shop scheduling problem with total weighted tardiness objective (JSPTWT). This objective reflects the goal to achieve a high service level which is of increasing importance in many branches of industry. The paper concentrates on a class of baseline heuristics for this problem, known as neighborhood search techniques. An approach based on disjunctive graphs is developed to capture the general structure of neighborhoods for the JSPTWT. Existing as well as newly designed neighborhoods are formulated and analyzed. The performance and search ability of the operators (as well as combinations thereof) are compared in a computational study. Although no dominant operator is identified, a transpose-based perturbation on multiple machines turns out as a promising choice if applied as the only operator. Combining operators improves the schedule quality only slightly. But, the implementation of operators within a meta-heuristic enables to produce a higher schedule quality. A structural classification of neighborhood operators and some new analytical results are presented as well.     

A simulated annealing algorithm for single machine scheduling problems with family setups

Motivated by the real-life scheduling problem in a steel-wire factory in China, this paper studies the problem of minimizing the maximum lateness on a single machine with family setups. In view of the NP-hard nature of the problem, neighborhood properties of the problem are investigated. It is found that the traditional move-based neighborhood is inefficient to search. Then a new neighborhood, which is based on batch destruction and construction, is developed. A simulated annealing algorithm with the new neighborhood is proposed. Experiments are carried out on the randomly generated problems and the real-life instances from a factory in China. Computational results show that the proposed algorithm can obtain better near optimal solutions than the existing algorithm.     

A GES/TS algorithm for the job shop scheduling

The job shop scheduling problem is a difficult combinatorial optimization problem. This paper presents a hybrid algorithm which combines global equilibrium search, path relinking and tabu search to solve the job shop scheduling problem. The proposed algorithm used biased random sampling to have a better covering of the solution space. In addition, a new version of N6 neighborhood is applied in a tabu search framework. In order to evaluate the algorithm, comprehensive tests are applied to it using various standard benchmark sets. Computational results confirm the effectiveness of the algorithm and its high speed. Besides, 19 new upper bounds among the unsolved problems are found.     

A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems

This paper addresses the flexible job shop scheduling problem (fJSP) with three objectives: min makespan, min maximal machine workload and min total workload. We developed a hybrid genetic algorithm (GA) for the problem. The GA uses two vectors to represent solutions. Advanced crossover and mutation operators are used to adapt to the special chromosome structure and the characteristics of the problem. In order to strengthen the search ability, individuals of GA are first improved by a variable neighborhood descent (VND), which involves two local search procedures: local search of moving one operation and local search of moving two operations. Moving an operation is to delete the operation, find an assignable time interval for it, and allocate it in the assignable interval. We developed an efficient method to find assignable time intervals for the deleted operations based on the concept of earliest and latest event time. The local optima of moving one operation are further improved by moving two operations simultaneously. An extensive computational study on 181 benchmark problems shows the performance of our approach.     

A simulated annealing algorithm approach to hybrid flow shop scheduling with sequence-dependent setup times

One of the scheduling problems with various applications in industries is hybrid flow shop. In hybrid flow shop, a series of n jobs are processed at a series of g workshops with several parallel machines in each workshop. To simplify the model construction in most research on hybrid flow shop scheduling problems, the setup times of operations have been ignored, combined with their corresponding processing times, or considered non sequence-dependent. However, in most real industries such as chemical, textile, metallurgical, printed circuit board, and automobile manufacturing, hybrid flow shop problems have sequence-dependent setup times (SDST). In this research, the problem of SDST hybrid flow shop scheduling with parallel identical machines to minimize the makespan is studied. A novel simulated annealing (NSA) algorithm is developed to produce a reasonable manufacturing schedule within an acceptable computational time. In this study, the proposed NSA uses a well combination of two moving operators for generating new solutions. The obtained results are compared with those computed by Random Key Genetic Algorithm (RKGA) and Immune Algorithm (IA) which are proposed previously. The results show that NSA outperforms both RKGA and IA.