An improved scatter search algorithm for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times

In this paper, a scatter search algorithm with improved component modules is proposed to solve the single machine total weighted tardiness problem with sequence-dependent setup times. For diversification generation module, both random strategy based heuristics and construction heuristic are adopted to generate the diversified population. For improvement module, variable neighborhood search based local searches are embedded into the algorithm to improve the trial solutions and the combined solutions. For reference set update module, the number of edges by which the two solutions differ from each other is counted to measure the diversification value between two solutions. We also propose a new strategy in which the length of the reference set could be adjusted adaptively to balance the computing time and solving ability. In addition, a discrete differential evolution operator is proposed with another two operators constitute the combination module to generate the new trial solutions with the solutions in the subsets. The proposed algorithm is tested on the 120 benchmark instances from the literature. Computational results indicate that the average relative percentage deviations of the improved algorithm from the ACO_AP, DPSO, DDE and GVNS are −5.16%, −3.33%, −1.81% and −0.08%, respectively. Comparing with the state-of-the-art and exact algorithms, the proposed algorithm can obtain 78 optimal solutions out of 120 instances within a reasonable computational time.     

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.     

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.     

Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective

This paper presents several search heuristics and their performance in batch scheduling of parallel, unrelated machines. Identical or similar jobs are typically processed in batches in order to decrease setup times and/or processing times. The problem accounts for allotting batched work parts into unrelated parallel machines, where each batch consists of a fixed number of jobs. Some batches may contain different jobs but all jobs within each batch should have an identical processing time and a common due date. Processing time of each job of a batch is determined according to the machine group as well as the batch group to which the job belongs. Major or minor setup times are required between two subsequent batches depending on batch sequence but are independent of machines. The objective of our study is to minimize the total weighted tardiness for the unrelated parallel machine scheduling. Four search heuristics are proposed to address the problem, namely (1) the earliest weighted due date, (2) the shortest weighted processing time, (3) the two-level batch scheduling heuristic, and (4) the simulated annealing method. These proposed local search heuristics are tested through computational experiments with data from dicing operations of a compound semiconductor manufacturing facility.     

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.     

Iterated Local Search for single-machine scheduling with sequence-dependent setup times to minimize total weighted tardiness

We present an Iterated Local Search (ILS) algorithm for solving the single-machine scheduling problem with sequence-dependent setup times to minimize the total weighted tardiness. The proposed ILS algorithm exhibits several distinguishing features, including a new neighborhood structure called Block Move and a fast incremental evaluation technique, for evaluating neighborhood solutions. Applying the proposed algorithm to solve 120 public benchmark instances widely used in the literature, we achieve highly competitive results compared with a recently proposed exact algorithm and five sets of best solutions of state-of-the-art metaheuristic algorithms in the literature. Specifically, ILS obtains the optimal solutions for 113 instances within a reasonable time, and it outperforms the previous best-known results obtained by metaheuristic algorithms for 34 instances and matches the best results for 82 instances. In addition, ILS is able to obtain the optimal solutions for the remaining seven instances under a relaxed time limit, and its computational efficiency is comparable with the state-of-the-art exact algorithm by Tanaka and Araki (Comput Oper Res 40:344–352, 2013). Finally, on analyzing some important features that affect the performance of ILS, we ascertain the significance of the proposed Block Move neighborhood and the fast incremental evaluation technique.     

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

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

带准备时间的单机调度问题的混合进化算法研究

提出了一种混合进化算法（HEA）用于求解具有序列相关依赖且带准备时间的单机调度问题, 其优化目标为最小化总延迟。该混合进化算法由局部搜索和进化算法框架混合而成。HEA具有一些新的特点, 例如在局部搜索中采用了一种新提出的基于块移动的邻域结构, 这种邻域结构合理地限制了搜索空间, 提高了算法的搜索效率; 在HEA中采用了一种新的组合算子——块顺序交叉算符（BOX）来产生新的子代工作序列。用本算法对当前国际文献中公开的两组共64个算例进行了测试, HEA改进了9个算例在当前文献中的最优解, 表明了所提出的HEA算法的优越性。与之前的国际文献中最好的四个启发式算法进行了详细比较, 表明了HEA算法的优势。     

A hybrid genetic algorithm for parallel machine scheduling with setup times

Journal of Intelligent Manufacturing - This paper addresses the unrelated parallel machine scheduling problem with sequence and machine dependent setup times and machine eligibility constraints....     

Makespan minimization for scheduling unrelated parallel machines with setup times

This study considers the problem of scheduling jobs on unrelated parallel machines with machine-dependent and job sequence-dependent setup times. In this study, a restricted simulated annealing (RSA) algorithm which incorporates a restricted search strategy is presented to minimize the makespan. The proposed RSA algorithm can effective reduce the search effort required to find the best neighborhood solution by eliminating ineffective job moves. The effectiveness and efficiency of the proposed RSA algorithm is compared with the basic simulated annealing and existing meta-heuristics on a benchmark problem dataset used in earlier studies. Computational results indicate that the proposed RSA algorithm compares well with the state-of-the-art meta-heuristic for small-sized problems, and significantly outperforms basic simulated annealing algorithm and existing algorithms for large-sized problems.     

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.     

An efficient hybrid genetic algorithm to solve assembly line balancing problem with sequence-dependent setup times

In this paper the setup assembly line balancing and scheduling problem (SUALBSP) is considered. Since this problem is NP-hard, a hybrid genetic algorithm (GA) is proposed to solve the problem. This problem involves assigning the tasks to the stations and scheduling them inside each station. A simple permutation is used to determine the sequence of tasks. To determine the assignment of tasks to stations, the algorithm is hybridized using a dynamic programming procedure. Using dynamic programming, at any time a chromosome can be converted to an optimal solution (subject to the chromosome sequence).     

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.     

A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times

This paper is concerned with solving the single machine total weighted tardiness problem with sequence dependent setup times by a discrete differential evolution algorithm developed by the authors recently. Its performance is enhanced by employing different population initialization schemes based on some constructive heuristics such as the well-known NEH and the greedy randomized adaptive search procedure (GRASP) as well as some priority rules such as the earliest weighted due date (EWDD) and the apparent tardiness cost with setups (ATCS). Additional performance enhancement is further achieved by the inclusion of a referenced local search (RLS) in the algorithm together with the use of destruction and construction (DC) procedure when obtaining the mutant population. Furthermore, to facilitate the greedy job insertion into a partial solution which will be employed in the NEH, GRASP, DC heuristics as well as in the RLS local search, some newly designed speed-up methods are presented for the insertion move for the first time in the literature. They are novel contributions of this paper to the single machine tardiness related scheduling problems with sequence dependent setup times. To evaluate its performance, the discrete differential evolution algorithm is tested on a set of benchmark instances from the literature. Through the analyses of experimental results, its highly effective performance with substantial margins both in solution quality and CPU time is shown against the best performing algorithms from the literature, in particular, against the very recent newly designed particle swarm and ant colony optimization algorithms of Anghinolfi and Paolucci [A new discrete particle swarm optimization approach for the single machine total weighted tardiness scheduling problem with sequence dependent setup times. European Journal of Operational Research 2007; doi:10.1016/j.ejor.2007.10.044] and Anghinolfi and Paolucci [A new ant colony optimization approach for the single machine total weighted tardiness scheduling problem. http://www.discovery.dist.unige.it/papers/Anghinolfi_Paolucci_ACO.pdf, respectively. Ultimately, 51 out of 120 overall aggregated best known solutions so far in the literature are further improved while other 50 instances are solved equally.     

An efficient weighted bi-objective scheduling algorithm for heterogeneous systems

This paper proposes the Makespan and Reliability Cost Driven (MRCD) heuristic, a static scheduling strategy for heterogeneous distributed systems that not only minimizes the makespan, but also maximizes the reliability of the application. The MRCD scheduling decisions are guided by a weighted function that considers both objectives simultaneously, instead of prioritizing one of them. This work also introduces a classification of the solutions produced by weighted bi-objective schedulers to aid users to tune the weighting function such that an appropriate solution can be selected in accordance with their needs. In comparison with the related work, MRCD produced schedules with makespans that were significantly better then those produced by the other strategies at expense of an insignificant deterioration in reliability.     

Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness

In many realistic production situations, a job processed later consumes more time than the same job when it is processed earlier. Production scheduling in such an environment is known as scheduling with deteriorating jobs. However, research on scheduling problems with deteriorating jobs has rarely considered explicit (separable) setup time (cost). In this paper, we consider a single-machine scheduling problem with deteriorating jobs and setup times to minimize the maximum tardiness. We provide a branch-and-bound algorithm to solve this problem. Computational experiments show that the algorithm can solve instances up to 1000 jobs in reasonable time.     

An efficient hybrid algorithm for resource-constrained project scheduling

We propose an efficient hybrid algorithm, known as ACOSS, for solving resource-constrained project scheduling problems (RCPSP) in real-time. The ACOSS algorithm combines a local search strategy, ant colony optimization (ACO), and a scatter search (SS) in an iterative process. In this process, ACO first searches the solution space and generates activity lists to provide the initial population for the SS algorithm. Then, the SS algorithm builds a reference set from the pheromone trails of the ACO, and improves these to obtain better solutions. Thereafter, the ACO uses the improved solutions to update the pheromone set. Finally in this iteration, the ACO searches the solution set using the new pheromone trails after the SS has terminated. In ACOSS, ACO and the SS share the solution space for efficient exchange of the solution set. The ACOSS algorithm is compared with state-of-the-art algorithms using a set of standard problems available in the literature. The experimental results validate the efficiency of the proposed algorithm.     

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.