Unrelated parallel machine scheduling with setup times using simulated annealing

This paper presents a scheduling problem for unrelated parallel machines with sequence-dependent setup times, using simulated annealing (SA). The problem accounts for allotting work parts of L jobs into M parallel unrelated machines, where a job refers to a lot composed of N items. Some jobs may have different items while every item within each job has an identical processing time with a common due date. Each machine has its own processing times according to the characteristics of the machine as well as job types. Setup times are machine independent but job sequence dependent. SA, a meta-heuristic, is employed in this study to determine a scheduling policy so as to minimize total tardiness. The suggested SA method utilizes six job or item rearranging techniques to generate neighborhood solutions. The experimental analysis shows that the proposed SA method significantly outperforms a neighborhood search method in terms of total tardiness.     

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.     

A heuristic algorithm to minimize total weighted tardiness on a single machine with release times

This paper attempts to solve a single machine‐scheduling problem, in which the objective function is to minimize the total weighted tardiness with different release dates of jobs. To address this scheduling problem, a heuristic scheduling algorithm is presented. A mathematical programming formulation is also formulated to validate the performance of the heuristic scheduling algorithm proposed herein. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. Overall, this algorithm can find the optimal solutions for 2200 out of 2400 randomly generated problems (91.67%). For the most complicated 20 job cases, it requires less than 0.0016 s to obtain an ultimate or even optimal solution. This heuristic scheduling algorithm can therefore efficiently solve this kind of problem.     

Single CNC machine scheduling with controllable processing times to minimize total weighted tardiness

Advanced manufacturing technologies, such as CNC machines, require significant investments, but also offer new capabilities to the manufacturers. One of the important capabilities of a CNC machine is the controllable processing times. By using this capability, the due date requirements of customers can be satisfied much more effectively. Processing times of the jobs on a CNC machine can be easily controlled via machining conditions such that they can be increased or decreased at the expense of tooling cost. Since scheduling decisions are very sensitive to the processing times, we solve the process planning and scheduling problems simultaneously. In this study, we consider the problem of scheduling a set of jobs on a single CNC machine to minimize the sum of total weighted tardiness, tooling and machining costs. We formulated the joint problem, which is NP-hard since the total weighted tardiness problem (with fixed processing times) is strongly NP-hard alone, as a nonlinear mixed integer program. We proposed a DP-based heuristic to solve the problem for a given sequence and designed a local search algorithm that uses it as a base heuristic.     

Dominance rules for the parallel machine total weighted tardiness scheduling problem with release dates

We address the parallel machine total weighted tardiness scheduling problem with release dates. We describe dominance rules and filtering methods for this problem. Most of them are adaptations of dominance rules based on solution methods for the single-machine problem. We show how it is possible to deduce whether or not certain jobs can be processed by a particular machine in a particular context and we describe techniques that use this information to improve the dominance rules. On the basis of these techniques we describe an enumeration procedure and we provide experimental results to determine the effectiveness of the dominance rules.     

A population-based variable neighborhood search for the single machine total weighted tardiness problem

This paper investigates the single machine total weighted tardiness problem, in which a set of independent jobs with distinct processing times, weights, and due dates are to be scheduled on a single machine to minimize the sum of weighted tardiness of all jobs. This problem is known to be strongly NP-hard, and thus provides a challenging area for metaheuristics. A population-based variable neighborhood search (PVNS) algorithm is developed to solve it. This algorithm differs from the basic variable neighborhood search (VNS). First, the PVNS consists of a number of iterations of the basic VNS, and in each iteration a population of solutions is used to simultaneously generate multiple trial solutions in a neighborhood so as to improve the search diversification. Second, the PVNS adopts a combination of path-relinking, variable depth search and tabu search to act as the local search procedure so as to improve the search intensification. Computational experiments show that the proposed PVNS algorithm can obtain the optimal or best known solutions within a reasonable computation time for all standard benchmark problem instances from the literature.     

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.     

Minimizing total tardiness and earliness on unrelated parallel machines with controllable processing times

Job scheduling has always been a challenging task in modern manufacturing and the most real life scheduling problems which involves multi-criteria and multi-machine environments. In this research our direction is largely motivated by the adoption of the Just-In-Time (JIT) philosophy in parallel machines system, where processing times of jobs are controllable. The goal of this paper is to minimize total weighted tardiness and earliness besides jobs compressing and expanding costs, depending on the amount of compression/expansion as well as maximum completion time called makespan simultaneously. Jobs due dates are distinct and no inserted idle time is allowed after starting machine processing. Also each machine is capable of processing only some predetermined jobs and operations with probably different speeds. A Mixed Integer Programming (MIP) model is proposed to formulate such a problem and is solved optimally in small size instances. A Parallel Net Benefit Compression-Net Benefit Expansion (PNBC–NBE) heuristic is then presented to acquire the optimal jobs set amount of compression and expansion processing times in a given sequence. To solve medium-to-large size cases, a proposed heuristic, two meta-heuristics and a hybrid technique are also employed. Experimental results demonstrate that our hybrid procedure is a proficient method and could efficiently solve such complicated problems.     

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.     

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.     

Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach

This work proposes a hybrid metaheuristic (HMH) approach which integrates several features from tabu search (TS), simulated annealing (SA) and variable neighbourhood search (VNS) in a new configurable scheduling algorithm. In particular, either a deterministic or a random candidate list strategy can be used to generate the neighbourhood of a solution, both a tabu list mechanism and the SA probabilistic rule can be adopted to accept solutions, and the dimension of the explored neighbourhood can be dynamically modified. The considered class of scheduling problems is characterized by a set of independent jobs to be executed on a set of parallel machines with non-zero ready times and sequence dependent setups. In particular, the NP-hard generalized parallel machine total tardiness problem (GPMTP) recently defined by Bilge et al. [A tabu search algorithm for parallel machine total tardiness problem. Computers & Operations Research 2004;31:397–414], is faced. Several alternative configurations of the HMH have been tested on the same benchmark set used by Bilge et al. The results obtained highlight the appropriateness of the proposed approach.     

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.     

Minimizing mean weighted tardiness in unrelated parallel machine scheduling with reinforcement learning

We address an unrelated parallel machine scheduling problem with R-learning, an average-reward reinforcement learning (RL) method. Different types of jobs dynamically arrive in independent Poisson processes. Thus the arrival time and the due date of each job are stochastic. We convert the scheduling problems into RL problems by constructing elaborate state features, actions, and the reward function. The state features and actions are defined fully utilizing prior domain knowledge. Minimizing the reward per decision time step is equivalent to minimizing the schedule objective, i.e. mean weighted tardiness. We apply an on-line R-learning algorithm with function approximation to solve the RL problems. Computational experiments demonstrate that R-learning learns an optimal or near-optimal policy in a dynamic environment from experience and outperforms four effective heuristic priority rules (i.e. WSPT, WMDD, ATC and WCOVERT) in all test problems.     

并行机成组调度问题的启发式算法

研究了优化目标为总拖后/提前时间最小化的并行机成组调度问题,提出了一种三阶段启发式近似求解算法。首先把并行机问题看成单机问题,以最小化总拖后时间为优化目标排列工件的加工次序;然后将工件按第一阶段所求得的次序指派到最先空闲的并行的机器上;最后采用改进的GTW算法对各机器上的工件调度插入适当的空闲时间。计算表明该算法能够在很短的时间内给出大规模调度问题的近似最优解。     

The single-machine total weighted tardiness scheduling problem with position-based learning effects

This study addresses the problem of minimizing the total weighted tardiness on a single-machine with a position-based learning effect. Several dominance properties are established to develop branch and bound algorithm and a lower bound is provided to derive the optimal solution. In addition, three heuristic procedures are developed for near-optimal solutions. Computational results are also presented to evaluate the performance of the proposed algorithms.     

A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem

This paper considers the job-shop problem with release dates and due dates, with the objective of minimizing the total weighted tardiness. A genetic algorithm is combined with an iterated local search that uses a longest path approach on a disjunctive graph model. A design of experiments approach is employed to calibrate the parameters and operators of the algorithm. Previous studies on genetic algorithms for the job-shop problem point out that these algorithms are highly depended on the way the chromosomes are decoded. In this paper, we show that the efficiency of genetic algorithms does no longer depend on the schedule builder when an iterated local search is used. Computational experiments carried out on instances of the literature show the efficiency of the proposed algorithm.     

Minimizing total earliness and tardiness through unrelated parallel machine scheduling using distributed release time control

Using unrelated parallel machine scheduling to minimize the total earliness and tardiness of jobs with distinct due dates is a nondeterministic polynomial-hard problem. Delayed customer orders may result in penalties and reduce customer satisfaction. On the other hand, early completion creates inventory storage costs, which increase the total cost. Although parallel machines can increase productivity, machine assignments also increase the complexity of production. Therefore, the challenge in parallel machine scheduling is to dynamically adjust the machine assignment to complete the job within the shortest possible time. In this paper, we address an unrelated parallel machine scheduling problem for jobs with distinct due dates and dedicated machines. The objective is to dynamically allocate jobs to unrelated parallel machines in order to minimize the total earliness and tardiness time. We formulate the problem as a mixed integer linear programming (MILP) model and develop a modified genetic algorithm (GA) with a distributed release time control (GARTC) mechanism to obtain the near-optimal solution. A preliminary computational study indicates that the developed GARTC not only provides good quality solutions within a reasonable amount of time, but also outperforms the MILP model, a classic GA and heuristic approaches described in the literature.     

Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects

In this paper, we study an unrelated parallel machine scheduling problem with setup time and learning effects simultaneously. The setup time is proportional to the length of the already processed jobs. That is, the setup time of each job is past-sequence-dependent. The objectives are to minimize the total absolute deviation of job completion times and the total load on all machines, respectively. We show that the proposed problem is polynomially solvable. We also discuss two special cases of the problem and show that they can be optimally solved by lower order algorithms.     

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.