A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times

We present a systematic comparison of hybrid evolutionary algorithms (HEAs), which independently use six combinations of three crossover operators and two population updating strategies, for solving the single machine scheduling problem with sequence-dependent setup times. Experiments show the competitive performance of the combination of the linear order crossover operator and the similarity-and-quality based population updating strategy. Applying the selected HEA to solve 120 public benchmark instances of the single machine scheduling problem with sequence-dependent setup times to minimize the total weighted tardiness widely used in the literature, we achieve highly competitive results compared with the exact algorithm and other state-of-the-art metaheuristic algorithms in the literature. Meanwhile, we apply the selected HEA in its original form to deal with the unweighted 64 public benchmark instances. Our HEA is able to improve the previous best known results for one instance and match the optimal or the best known results for the remaining 63 instances in a reasonable time.     

A realistic variant of bi-objective unrelated parallel machine scheduling problem: NSGA-II and MOACO approaches

The problem investigated in this study involves an unrelated parallel machine scheduling problem with sequence-dependent setup times, different release dates, machine eligibility and precedence constraints. This problem has been inspired from a realistic scheduling problem in the shipyard. The optimization criteria are to simultaneously minimize mean weighted flow time and mean weighted tardiness. To formulate this complicated problem, a new mixed-integer programming model is presented. Considering the NP-complete characteristic of this problem, two famous meta-heuristics including a non-dominated sorting genetic algorithm (NSGA-II) and a multi-objective ant colony optimization (MOACO) which is a modified and adaptive version of BicriterionAnt algorithm are developed. Obviously, the precedence constraints increase the complexity of the scheduling problem in strong sense in order to generate feasible solutions, especially in parallel machine environment. Therefore a new corrective algorithm is proposed to obtain the feasibility in all stages of the algorithms. Due to the fact that appropriate design of parameter has a significant effect on the performance of algorithms, we calibrate the parameters of these algorithms by using new approach of Taguchi method. The performances of the proposed meta-heuristics are evaluated by a number of numerical examples. The results indicated that the suggested MOACO statistically outperformed the proposed NSGA-II in solving the test problems. In addition, the application of the proposed algorithms is justified by a real block erection scheduling problem in the shipyard.     

A two-stage Ant Colony Optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times

This paper addresses the non-preemptive unrelated parallel machine scheduling problem with machine-dependent and sequence-dependent setup times. All jobs are available at time zero, all times are deterministic, and the objective is to minimize the makespan. An Ant Colony Optimization (ACO) algorithm is introduced in this paper and is applied to this NP-hard problem; in particular, the proposed ACO tackles a special structure of the problem, where the ratio of the number of jobs to the number of machines is large (i.e., for a highly utilized set of machines). Its performance is evaluated by comparing its solutions to solutions obtained using Tabu Search and other existing heuristics for the same problem, namely the Partitioning Heuristic and Meta-RaPS. The results show that ACO outperformed the other algorithms.     

An iterated greedy algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times

This article presents an enhanced iterated greedy (EIG) algorithm that searches both insert and swap neighbourhoods for the single-machine total weighted tardiness problem with sequence-dependent setup times. Novel elimination rules and speed-ups are proposed for the swap move to make the employment of swap neighbourhood worthwhile due to its reduced computational expense. Moreover, a perturbation operator is newly designed as a substitute for the existing destruction and construction procedures to prevent the search from being attracted to local optima. To validate the proposed algorithm, computational experiments are conducted on a benchmark set from the literature. The results show that the EIG outperforms the existing state-of-the-art algorithms for the considered problem.     

A memetic algorithm-based heuristic for a scheduling problem in printed circuit board assembly

This research develops a memetic algorithm to solve Printed Circuit Board (PCB) scheduling with sequence-dependent setup times on a single machine with constrained feeder capacity. The objective of the scheduling problem is to minimize the total weighted tardiness. A memetic algorithm-based heuristics is developed by integrating a genetic algorithm, Minimum Slack Time (MST) scheduling rule, “Keep Tool Needed Soonest” (KTNS) policy, and a local search procedure. Application of the MA results in two outcome plans: a scheduling plan and a feeder setup plan.Numerical experiments show that compared to a number of commonly used dispatching rules, the memetic algorithm provides better solutions in term of minimum total weighted tardiness. Even the computation is the highest, it still practical. Calibration of MA parameter values is also explored in this study.     

顺序依赖的调整时间和拖期的无缝钢管热轧批量调度算法

无缝钢管热轧生产存在一类特殊的顺序依赖机器调整时间,调整时间依赖于相邻轧制批量间的规格切换,与批量间规格呈线性函数关系.针对具有此类调整时间的热轧批量调度问题,进一步考虑交货期要求,探讨了调整时间与交货期之间的性质特征,并以最小化总机器调整时间和最小化总拖期为目标,基于进化算法框架设计了快速重排序邻域搜索多目标算法(f...     

A fuzzy-mixed-integer goal programming model for a parallel-machine scheduling problem with sequence-dependent setup times and release dates

This paper presents a new mixed-integer goal programming (MIGP) model for a parallel-machine scheduling problem with sequence-dependent setup times and release dates. Two objectives are considered in the model to minimize the total weighted flow time and the total weighted tardiness simultaneously. Due to the complexity of the above model and uncertainty involved in real-world scheduling problems, it is sometimes unrealistic or even impossible to acquire exact input data. Hence, we consider the parallel-machine scheduling problem with sequence-dependent set-up times under the hypothesis of fuzzy processing time's knowledge and two fuzzy objectives as the MIGP model. In addition, a quite effective and applicable methodology for solving the above fuzzy model are presented. At the end, the effectiveness of the proposed model and the denoted methodology is demonstrated through some test problems.     

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.     

A discrete electromagnetism-like mechanism for single machine total weighted tardiness problem with sequence-dependent setup times

Electromagnetism-like mechanism (EM) is a novel meta-heuristic, inspired by the attraction–repulsion mechanism of electromagnetic theory. There are very few applications of EM in scheduling problems. This paper presents a discrete EM (DEM) algorithm for minimizing the total weighted tardiness in a single-machine scheduling problem with sequence-dependent setup times. Unlike other discrete EM algorithms that use a random key method to deal with the discreteness, the proposed DEM algorithm employs a completely different approach, with an attraction–repulsion mechanism involving crossover and mutation operators. The proposed algorithm not only accomplishes the intention of an EM algorithm but also can be applied in other combinatorial optimization problems. To verify the algorithm, it is compared with a discrete differential evolution (DDE) algorithm, which is the best meta-heuristic for the considered problem. Computational experiments show that the performance of the proposed DEM algorithm is better than that of the DDE algorithm in most benchmark problem instances. Specifically, 30 out of 120 aggregated best-known solutions in the literature are further improved by the DEM algorithm, while other another 70 instances are solved to an equivalent degree.     

Minimizing total tardiness in a two-machine re-entrant flowshop with sequence-dependent setup times

We consider a two-machine re-entrant flowshop scheduling problem in which all jobs must be processed twice on each machine and there are sequence-dependent setup times on the second machine. For the problem with the objective of minimizing total tardiness, we develop dominance properties and a lower bound by extending those for a two-machine re-entrant flowshop problem (without sequence-dependent setup times) as well as heuristic algorithms, and present a branch and bound algorithm in which these dominance properties, lower bound, and heuristics are used. For evaluation of the performance of the branch and bound algorithm and heuristics, computational experiments are performed on randomly generated instances, and results are reported.     

Modeling and scheduling a case of flexible flowshops: Total weighted tardiness minimization

Two of the most realistic assumptions in the field of scheduling are the consideration of setup and transportation times. In this paper, we study the flexible flowshop scheduling where setup times are anticipatory sequence-dependent and transportation times are job-independent. We also assume that there are several transporters to carry jobs. The objective is to minimize total weighted tardiness. We first formulate the problem as a mixed integer linear programming (MILP) model. With this, we solve small-sized instances to optimality. Since this problem is known to be NP-hard, we then propose an effective metaheuristic to tackle large-sized instances. This metaheuristic, called electromagnetism algorithm (EMA), originates from the attraction–repulsion mechanism of the electromagnetism theory. We conduct a series of experiments and complete statistical analyses to evaluate the performance of the proposed MILP model and EMA. On a set of instances, we first tune the parameters of EMA. Then, the efficiency of the model and general performance of the proposed EMA are assessed over a set of small-sized instances. To further evaluate EMA, we compare it against two high performing metaheuristics existing in the literature over a set of large-sized instances. The results demonstrate that the proposed MILP model and EMA are effective for this problem.     

Bi-objective parallel machines scheduling with sequence-dependent setup times using hybrid metaheuristics and weighted min–max technique

In the literature of multi-objective problem, there are different algorithms to solve different optimization problems. This paper presents a min–max multi-objective procedure for a dual-objective, namely make span, and sum of the earliness and tardiness of jobs in due window machine scheduling problems, simultaneously. In formulation of min–max method when this method is combined with the weighting method, the decision maker can have the flexibility of mixed use of weights and distance parameter to yield a set of Pareto-efficient solutions. This research extends the new hybrid metaheuristic (HMH) to solve parallel machines scheduling problems with sequence-dependent setup time that comprises three components: an initial population generation method based on an ant colony optimization (ACO), a simulated annealing (SA) as an evolutionary algorithm employs certain probability to avoid becoming trapped in a local optimum, and a variable neighborhood search (VNS) which involves three local search procedures to improve the population. In addition, two VNS-based HMHs, which are a combination of two methods, SA/VNS and ACO/VNS, are also proposed to solve the addressed scheduling problems. A design of experiments approach is employed to calibrate the parameters. The non-dominated sets obtained from HMH and two best existing bi-criteria scheduling algorithms are compared in terms of various indices and the computational results show that the proposed algorithm is capable of producing a number of high-quality Pareto optimal scheduling plans. Aside, an extensive computational experience is carried out to analyze the different parameters of the algorithm.     

An efficient memetic algorithm for total weighted tardiness minimization in a single machine with setups

The single machine scheduling problem with sequence-dependent setup times with the objective of minimizing the total weighted tardiness is a challenging problem due to its complexity, and has a huge number of applications in real production environments. In this paper, we propose a memetic algorithm that combines and extends several ideas from the literature, including a crossover operator that respects both the absolute and relative position of the tasks, a replacement strategy that improves the diversity of the population, and an effective but computationally expensive neighborhood structure. We propose a new decomposition of this neighborhood that can be used by a variable neighborhood descent framework, and also some speed-up methods for evaluating the neighbors. In this way we can obtain competitive running times. We conduct an experimental study to analyze the proposed algorithm and prove that it is significantly better than the state-of-the-art in standard benchmarks.     

An efficient hybrid evolutionary algorithm for scheduling with setup times and weighted tardiness minimization

We confront the job shop scheduling problem with sequence-dependent setup times and weighted tardiness minimization. To solve this problem, we propose a hybrid metaheuristic that combines the intensification capability of tabu search with the diversification capability of a genetic algorithm which plays the role of long term memory for tabu search in the combined approach. We define and analyze a new neighborhood structure for this problem which is embedded in the tabu search algorithm. The efficiency of the proposed algorithm relies on some elements such as neighbors filtering and a proper balance between intensification and diversification of the search. We report results from an experimental study across conventional benchmarks, where we analyze our approach and demonstrate that it compares favorably to the state-of-the-art methods.     

An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times

This study proposes an exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. The algorithm is an extension of the authors' previous algorithm for the single-machine scheduling problem without setup times, which is based on the SSDP (Successive Sublimation Dynamic Programming) method. In the first stage of the algorithm, the conjugate subgradient algorithm or the column generation algorithm is applied to a Lagrangian relaxation of the original problem to adjust multipliers. Then, in the second stage, constraints are successively added to the relaxation until the gap between lower and upper bounds becomes zero. The relaxation is solved by dynamic programming and unnecessary dynamic programming states are eliminated to suppress the increase of computation time and memory space. In this study a branching scheme is integrated into the algorithm to manage to solve hard instances. The proposed algorithm is applied to benchmark instances in the literature and almost all of them are optimally solved.     

A discrete colonial competitive algorithm for hybrid flowshop scheduling to minimize earliness and quadratic tardiness penalties

Recently introduced colonial competitive algorithm (CCA) has shown its excellent capability on different optimization problems. The aim of this paper is to propose a discrete version of this method to determine a schedule that minimizes sum of the linear earliness and quadratic tardiness in the hybrid flowshops scheduling problem with simultaneously considering effects of sequence-dependent setup times and limited waiting time. In other word we assume that the waiting time for each job between two consecutive stages cannot be greater than a given upper bound. Also for this problem, a mixed integer program is formulated. Computational results are presented to evaluate the performance of the proposed algorithms for problems with different structures.     

An adaptive multi-population genetic algorithm to solve the multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times

In this paper we consider a multi-objective group scheduling problem in hybrid flexible flowshop with sequence-dependent setup times by minimizing total weighted tardiness and maximum completion time simultaneously. Whereas these kinds of problems are NP-hard, thus we proposed a multi-population genetic algorithm (MPGA) to search Pareto optimal solution for it. This algorithm comprises two stages. First stage applies combined objective of mentioned objectives and second stage uses previous stage’s results as an initial solution. In the second stage sub-population will be generated by re-arrangement of solutions of first stage. To evaluate performance of the proposed MPGA, it is compared with two distinguished benchmarks, multi-objective genetic algorithm (MOGA) and non-dominated sorting genetic algorithm II (NSGA-II), in three sizes of test problems: small, medium and large. The computational results show that this algorithm performs better than them.     

Scheduling algorithms for a semiconductor probing facility

This paper focuses on a scheduling problem in a semiconductor wafer probing facility. In the probing facility, wafer lots with distinct ready times are processed on a series of workstations, each with identical parallel machines. We develop a heuristic algorithm for the problem with the objective of minimizing total tardiness of orders. The algorithm employs a bottleneck-focused scheduling method, in which a schedule at the bottleneck workstation is constructed first and then schedules for other workstations are constructed based on the schedule at the bottleneck. For scheduling wafer lots at the bottleneck workstation, we consider prospective tardiness of the lots as well as sequence-dependent setup times required between different types of wafer lots. We also present a rolling horizon method for implementation of the scheduling method on a dynamic situation. The suggested methods are evaluated through a series of computational experiments and results show that the methods work better than existing heuristic methods.     

A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times

This paper presents a hybrid approach based on the integration between a genetic algorithm (GA) and concepts from constraint programming, multi-objective evolutionary algorithms and ant colony optimization for solving a scheduling problem. The main contributions are the integration of these concepts in a GA crossover operator. The proposed methodology is applied to a single machine scheduling problem with sequence-dependent setup times for the objective of minimizing the total tardiness. A sensitivity analysis of the hybrid approach is carried out to compare the performance of the GA and the hybrid genetic algorithm (HGA) approaches on different benchmarks from the literature. The numerical experiments demonstrate the HGA efficiency and effectiveness which generates solutions that approach those of the known reference sets and improves several lower bounds.     

Solving a bi-objective flowshop scheduling problem by a Multi-objective Immune System and comparing with SPEA2+ and SPGA

This paper presents a bi-objective flowshop scheduling problem with sequence-dependent setup times. The objective functions are to minimize the total completion time and the total earliness/tardiness for all jobs. An integer programming model is developed for the given problem that belongs to an NP-hard class. Thus, an algorithm based on a Multi-objective Immune System (MOIS) is proposed to find a locally Pareto-optimal frontier of the problem. To prove the efficiency of the proposed MOIS, different test problems are solved. Based on some comparison metrics, the computational results of the proposed MOIS is compared with the results obtained using two well-established multi-objective genetic algorithms, namely SPEA2+ and SPGA. The related results show that the proposed MOIS outperforms genetic algorithms, especially for the large-sized problems.