A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine

This paper deals with the single machine scheduling problem to minimize the total weighted tardiness in the presence of sequence dependent setup. Firstly, a mathematical model is given to describe the problem formally. Since the problem is NP-hard, a general variable neighborhood search (GVNS) heuristic is proposed to solve it. Initial solution for the GVNS algorithm is obtained by using a constructive heuristic that is widely used in the literature for the problem. The proposed algorithm is tested on 120 benchmark instances. The results show that 37 out of 120 best known solutions in the literature are improved while 64 instances are solved equally. Next, the GVNS algorithm is applied to single machine scheduling problem with sequence dependent setup times to minimize the total tardiness problem without changing any implementation issues and the parameters of the GVNS algorithm. For this problem, 64 test instances are solved varying from small to large sizes. Among these 64 instances, 35 instances are solved to the optimality, 16 instances' best-known results are improved, and 6 instances are solved equally compared to the best-known results. Hence, it can be concluded that the GVNS algorithm is an effective, efficient and a robust algorithm for minimizing tardiness on a single machine in the presence of setup times.     

History-dependent scheduling: Models and algorithms for scheduling with general precedence and sequence dependence

In this paper, we extend job scheduling models to include aspects of history-dependent scheduling, where setup times for a job are affected by the aggregate activities of all predecessors of that job. Traditional approaches to machine scheduling typically address objectives and constraints that govern the relative sequence of jobs being executed using available resources. This paper optimises the operations of multiple unrelated resources to address sequential and history-dependent job scheduling constraints along with time window restrictions. We denote this consolidated problem as the general precedence scheduling problem (GPSP). We present several applications of the GPSP and show that many problems in the literature can be represented as special cases of history-dependent scheduling. We design new ways to model this class of problems and then proceed to formulate it as an integer program. We develop specialized algorithms to solve such problems. An extensive computational analysis over a diverse family of problem data instances demonstrates the efficacy of the novel approaches and algorithms introduced in this paper.     

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.     

A robust hybrid approach based on particle swarm optimization and genetic algorithm to minimize the total machine load on unrelated parallel machines

This paper dealt with an unrelated parallel machines scheduling problem with past-sequence-dependent setup times, release dates, deteriorating jobs and learning effects, in which the actual processing time of a job on each machine is given as a function of its starting time, release time and position on the corresponding machine. In addition, the setup time of a job on each machine is proportional to the actual processing times of the already processed jobs on the corresponding machine, i.e., the setup times are past-sequence-dependent (p-s-d). The objective is to determine jointly the jobs assigned to each machine and the order of jobs such that the total machine load is minimized. Since the problem is NP-hard, optimal solution for the instances of realistic size cannot be obtained within a reasonable amount of computational time using exact solution approaches. Hence, an efficient method based on the hybrid particle swarm optimization (PSO) and genetic algorithm (GA), denoted by HPSOGA, is proposed to solve the given problem. In view of the fact that efficiency of the meta-heuristic algorithms is significantly depends on the appropriate design of parameters, the Taguchi method is employed to calibrate and select the optimal levels of parameters. The performance of the proposed method is appraised by comparing its results with GA and PSO with and without local search through computational experiments. The computational results for small sized problems show that the mentioned algorithms are fully effective and viable to generate optimal/near optimal solutions, but when the size of the problem is increased, the HPSOGA obtains better results in comparison with other algorithms.     

Satisfying due-dates in the presence of sequence dependent family setups with a special comedown structure

This paper addresses a static, n-job, single-machine scheduling problem with sequence dependent family setups. The setup matrix follows a special structure where a constant setup is required only if a job from a smaller indexed family is an immediate successor of one from a larger indexed family. The objective is to minimize the maximum lateness (L_max). A two-step neighborhood search procedure and an implicit enumeration scheme are proposed. Both procedures exploit the problem structure. The enumeration scheme produces optimum solutions to small and medium sized problems in reasonable computational times, yet it fails to perform efficiently in larger instances. Computational results show that the heuristic procedure is highly effective, and is efficient even for extremely large problems.     

一种用于车间作业调度问题的智能枚举算法

车间作业调度问题是优化组合中一个著名的难题,即使规模不大的算例,优化算法的时间也很长。文章提出了一种求解车间作业调度问题的快速智能枚举算法,选取了22个标准算例作为算法的测试试验集,该算法在较短的时间内找到了17个算例的最优解,试验结果表明智能枚举算法确实是一种快速的、有效的求解车间作业调度问题的近似算法。     

Solving a stochastic single machine problem with initial idle time and quadratic objective

We study a static single machine scheduling problem in which processing times are stochastic, due-dates and penalties for not completing jobs on time are deterministic, and an initial fixed idle time is allowed to be inserted before the processing of the first job begins on the machine. The objective is to determine the optimal sequence and the optimal initial idle time that jointly minimize the expected value of the sum of a quadratic cost function of idle time and the weighted sum of a quadratic function of job lateness. The problem is NP-hard to solve; however, we develop an exact algorithm based on a precedence relation structure among adjacent jobs. Our extensive computational results show that the algorithm can solve large problem instances quickly. We also demonstrate that the proposed problem is general in the sense that its special cases reduce to new stochastic models while its limiting cases simplify to some deterministic models.     

Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times

A scheduling problem with unrelated parallel machines, sequence and machine-dependent setup times, due dates and weighted jobs is considered in this work. A branch-and-bound algorithm (B&B) is developed and a solution provided by the metaheuristic GRASP is used as an upper bound. We also propose a set of instances for this type of problem. The results are compared to the solutions provided by two mixed integer programming models (MIP) with the solver CPLEX 9.0. We carry out computational experiments and the algorithm performs extremely well on instances with up to 30 jobs.     

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.     

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.     

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.     

Single-machine batch scheduling to minimize the total setup cost in the presence of deadlines

We address the single-machine batch scheduling problem with the objective of minimizing the total setup cost. This problem arises when there are n jobs that are partitioned into F families and when setup operations are required whenever the machine switches from processing a job of one family to processing a job of another family. We assume that setups do not require time but are associated with a fixed cost which is identical for all setup operations. Each job has a processing time and an associated deadline. The objective is to schedule all jobs such that they are on time with respect to their deadlines and the total setup cost is minimized. We show that the decision version of this problem is NP-complete in the strong sense. Furthermore, we present properties of optimal solutions and an \(O(n\log n+nF)\) algorithm that approximates the cost of an optimal schedule by a factor of F. The algorithm is analyzed in computational tests.     

MIP models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single server

This paper considers the identical parallel machines scheduling problem (PMSP) with a single server in charge of job setups. A job can be processed with a precedent setup by a server on one of the machines. The setup can be processed at only one machine at any time. In this paper, the problem P, S1|s_j|C_max with a general job set is formulated using mixed integer programming in two ways. The first one is developed by taking into account the characteristics of the single server problem, and the second one is developed by adding the concept of the server waiting time suggested by Abdekhodaee and Wirth (2002) [3]. Abdekhodaee and Wirth (2002) [3] define the equation of the server waiting time applied to only the special case with two machines and a regular job set. The general model for several machines is studied in this paper by developing the properties on the server waiting time. The hybrid heuristic algorithm is developed for the practical use, which can yield a near-optimal schedule in a reasonable computational time. The performance of algorithm is evaluated by comparing with the results of MIP models and heuristics appearing in the literature.     

A hybrid metaheuristic for the prize-collecting single machine scheduling problem with sequence-dependent setup times

This paper investigates a single machine scheduling problem with strong industrial background, named the prize-collecting single machine scheduling problem with sequence-dependent setup times. In this problem, there are n candidate jobs for processing in a single machine, each job has a weight (or profit) and a processing time, and during processing a symmetric sequence-dependent setup time exists between two consecutive jobs. Since there is a maximum available time limitation of the machine, it is generally impossible to complete the processing of all the candidate jobs within this time limitation. The objective is to find a job processing sequence of maximal job weights (or profits) over a subset of all candidate jobs whose makespan does not exceed the given time limitation. This problem can be considered as an application of the orienteering problem (OP) in the field of discrete manufacturing. We formulate this problem as a mixed integer linear programming (MILP) model and propose a hybrid metaheuristic combining the structures of scatter search and variable neighborhood search. Computational results on a large number of randomly generated instances with different structures show that the proposed hybrid metaheuristic outperforms CPLEX and two metaheuristics proposed for the OP.     

Single machine total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs

In this article, we consider a single machine scheduling problem with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the job processing time is defined by a function of its starting time and total normal processing time of jobs in front of it in the sequence. The objective is to determine an optimal schedule so as to minimize the total completion time. This problem remains open for the case of ?1?a?a denotes the learning index; we show that an optimal schedule of the problem is V-shaped with respect to job normal processing times. Three heuristic algorithms utilising the V-shaped property are proposed, and computational experiments show that the last heuristic algorithm performs effectively and efficiently in obtaining near-optimal solutions.     

A tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine

This paper introduces a tabu search heuristic for a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The problem consists in scheduling a set of dependent jobs, where the transition between two jobs comprises an unrestricted setup that can be performed at any time, and a restricted setup that must be performed outside of a given time interval which repeats daily in the same position. The setup time between two jobs is thus a function of the completion time of the first job. The tabu search heuristic relies on shift and swap moves, and a surrogate objective function is used to speed-up the neighborhood evaluation. Computational experiments show that the proposed heuristic consistently finds better solutions in less computation time than a recent branch-and-cut algorithm. Furthermore, on instances where the branch-and-cut algorithm cannot find the optimal solution, the heuristic always identifies a better solution.     

A competent memetic algorithm for complex scheduling

We face the job shop scheduling problem with sequence dependent setup times and makespan minimization by memetic algorithm. This algorithm combines a classic genetic algorithm with a local searcher. The performance of the local searcher relies on the combination of a tabu search algorithm with a neighborhood structure termed N ^S that are thoroughly described and analyzed. Also, two evolution models are considered: Lamarckian and Baldwinian evolution. We report results from an experimental study across conventional benchmark instances showing that the proposed algorithm outperforms the current state-of-the-art methods and that Lamarckian evolution is better than Baldwinian evolution.     

A dynamic programming formulation of a production sequencing problem

A dynamic programming algorithm is presented for determining an optimal solution to a problem where n jobs are to be sequenced in a two-stage production environment. Conditions are that the job sequence is the same in both stages; each job requires setups at each stage; setup times are sequence dependent; the second stage setups may overlap first stage production; and the optimal solutions is that with minimum overall duration. The recursion relation is developed, and computational schemes are described for obtaining the optimal solution or solutions. Computational experience is reported. The recursion relation is also extended to the case of any number of stages.     

A DP algorithm for minimizing makespan and total completion time on a series-batching machine

This paper studies a bicriteria scheduling problem on a series-batching machine with objective of minimizing makespan and total completion time simultaneously. A series-batching machine is a machine that can handle up to b jobs in a batch and the completion time of all jobs in a batch is equal to the finishing time of the last job in the batch and the processing time of a batch is the sum of the processing times of jobs in the batch. In addition, there is a constant setup time s for each batch. For the problem we can find all Pareto optimal solutions in O(n²) time by a dynamic programming algorithm, where n denotes the number of jobs.     

Lateness minimization with Tabu search for job shop scheduling problem with sequence dependent setup times

We tackle the job shop scheduling problem with sequence dependent setup times and maximum lateness minimization by means of a tabu search algorithm. We start by defining a disjunctive model for this problem, which allows us to study some properties of the problem. Using these properties we define a new local search neighborhood structure, which is then incorporated into the proposed tabu search algorithm. To assess the performance of this algorithm, we present the results of an extensive experimental study, including an analysis of the tabu search algorithm under different running conditions and a comparison with the state-of-the-art algorithms. The experiments are performed across two sets of conventional benchmarks with 960 and 17 instances respectively. The results demonstrate that the proposed tabu search algorithm is superior to the state-of-the-art methods both in quality and stability. In particular, our algorithm establishes new best solutions for 817 of the 960 instances of the first set and reaches the best known solutions in 16 of the 17 instances of the second set.