A decomposition algorithm for the single machine total tardiness problem

The problem of sequencing jobs on a single machine to minimize total tardiness is considered. An algorithm, which decomposes the problem into subproblems which are then solved by dynamic programming when they are sufficiently small, is presented and is tested on problems with up to 100 jobs.     

A new decomposition approach for the single machine total tardiness scheduling problem

This paper deals with the single machine total tardiness problem. From Emmons’ basic dominance conditions a new partition theorem is derived which generalises Lawler’s decomposition rule and leads to a new double decomposition procedure. This procedure is embedded into a branch and bound method which applies a new lower bound based on due dates reassignment. The branch and bound method is tested on problems with size up to 150 jobs.     

On the single machine total tardiness problem

In this paper we study the single machine total tardiness problem. We first identify some optimality properties based on which a special case with a given number of distinct due dates is proved polynomially solvable. The results are then extended to the case with release dates.     

Some remarks on the decomposition properties of the single machine total tardiness problem

The note extends Lawler’s [E.L. Lawler, A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness, Annals of Discrete Mathematics, 1 (1977) 331–342] fundamental decomposition theorem. This extension serves as a basis for alternate criteria that recognize when the problem is non-decomposable. It also shows that even relaxing a single criterion to a weak inequality may contradict Lawler’s (1977) decomposition theorem.     

New insights on the single machine total tardiness problem

Virtually all algorithmic studies on the single machine total tardiness problem use Emmons’ theorems that establish precedence relations between job pairs. In this paper, we investigate these theorems with a geometric viewpoint. This approach provides a compact way of representing Emmons’ theorems and promotes better insights into dominance properties. We use these insights to differentiate between certain classes of easy and hard instances.     

A memetic algorithm for the total tardiness single machine scheduling problem

In this paper, a new memetic algorithm (MA) for the total tardiness single machine scheduling (SMS) problem with due dates and sequence-dependent setup times is proposed. The main contributions with respect to the implementation of the hybrid population approach are a hierarchically structured population conceived as a ternary tree and the evaluation of three recombination operators. Concerning the local improvement procedure, several neighborhood reduction schemes are developed and proved to be effective when compared to the complete neighborhood. Results of computational experiments are reported for a set of randomly generated test problems. The memetic approach and a pure genetic algorithm (GA) version are compared with a multiple start algorithm that employs the all-pairs neighborhood as well as two constructive heuristics.     

Fast neighborhood search for the single machine total weighted tardiness problem

Most successful heuristics for solving 1||∑w_jT_j are based on swap moves. We present an algorithm which improves the complexity of searching the swap neighborhood from O(n³) to O(n²). We show that this result also improves the complexity of the recently developed dynasearch heuristics.     

A tabu search algorithm for the single machine total weighted tardiness problem

In this study, a tabu search (TS) approach to the single machine total weighted tardiness problem (SMTWT) is presented. The problem consists of a set of independent jobs with distinct processing times, weights and due dates to be scheduled on a single machine to minimize total weighted tardiness. The theoretical foundation of single machine scheduling with due date related objectives reveal that the problem is NP-hard, rendering it a challenging area for meta-heuristic approaches. This paper presents a totally deterministic TS algorithm with a hybrid neighborhood and dynamic tenure structure, and investigates the strength of several candidate list strategies based on problem specific characteristics in increasing the efficiency of the search. The proposed TS approach yields very high quality results for a set of benchmark problems obtained from the literature.     

Evaluation of greedy,myopic and less-greedy heuristics for the single machine,total tardiness problem

Simple, yet highly effective modifications to the net benefit of relocation (NBR) heuristic of Holsenback and Russell provide significant improvements in solution quality without any increase in computational effort by tempering the greedy nature of the original NBR heuristic. Two lemmas reduce the size of the search while adhering to optimality conditions. Experimentation compares the modified NBR heuristic (M-NBR) with the two leading heuristics of the literature. Testing on 25, 50 and 100-job problems over a wide range of due dates and tardiness factors shows the M-NBR algorithm to be the best single-pass heuristic to date. We show that a composite heuristic, employing the better of the M-NBR and another leading heuristic solution, consistently produces near-optimal solutions with negligible CPU requirements.     

Evaluation of leading heuristics for the single machine tardiness problem

A recent paper on the single machine tardiness problem by Panwalker, Smith and Koulamas [8] disputes experimental results of Holsenback and Russell [5] that indicated the Net Benefit of Relocation (NBR) heuristic provides significant improvement over the adjacent pairwise interchange (API) routine of Fry et al. [4], which in turn, was reported to show better solution quality than the Wilkerson-Irwin (W-I) heuristic ([13]). Panwalker et al. [8] claim that the P-S-K heuristic yields better results than the other methods over a wide range of problems and suggest that the NBR heuristic is not only inferior to the P-S-K heuristic, but also inferior to the API and W-I routines. This paper will shed new light on the quality of the experimentation of Panwalker et al. [8] and show that in general, the P-S-K heuristic is inferior to the NBR heuristic.     

Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one

We consider the problem of maximizing total tardiness on a single machine, where the first job starts at time zero and idle times between the processing of jobs are not allowed. We present a modification of an exact pseudo-polynomial algorithm based on a graphical approach, which has a polynomial running time. This result settles the complexity status of the problem under consideration which was open.     

Insights into two solution procedures for the single machine tardiness problem

This paper explores the well-known modified due date (MDD) rule for minimizing total tardiness on a single machine and shows that it has a decomposition structure. Based on this finding, we propose a decomposition heuristic and draw parallels to the famous optimal decomposition algorithm. We demonstrate that the MDD rule and the decomposition algorithm have striking similarities. We also discuss the key differences between these procedures. Finally, we present a sufficient condition under which the MDD rule is optimal and conclude the paper with some directions for future research.     

A tabu search approach for the single machine mean tardiness problem

In this paper, a tabu search approach is proposed for solving the single machine mean tardiness scheduling problem. Simulation experiment results obtained from the tabu search approach and three other heuristics are compared. Although computation time is increased, the results indicate that the proposed approach provides a much better solution than the other three approaches.     

Algorithms for single machine total tardiness scheduling with sequence dependent setups

We consider the problem of scheduling a single machine to minimize total tardiness with sequence dependent setup times. We present two algorithms, a problem space-based local search heuristic and a Greedy Randomized Adaptive Search Procedure (GRASP) for this problem. With respect to GRASP, our main contributions are—a new cost function in the construction phase, a new variation of Variable Neighborhood Search in the improvement phase, and Path Relinking using three different search neighborhoods. The problem space-based local search heuristic incorporates local search with respect to both the problem space and the solution space. We compare our algorithms with Simulated Annealing, Genetic Search, Pairwise Interchange, Branch and Bound and Ant Colony Search on a set of test problems from literature, showing that the algorithms perform very competitively.     

A controlled search simulated annealing method for the single machine weighted tardiness problem

In this paper, a new controlled search simulated annealing method is developed for addressing the single machine weighted tardiness problem. The proposed method is experimentally shown to solve optimally 99% of fifteen job problems with less than 0.2 CPU seconds, and to solve one hundred job problems as accurately as any existing methods, but with far less computational effort. This superior performance is achieved by using controlled search strategies that employ a good initial solution, a small neighborhood for local search, and acceptance probabilities of inferior solutions that are independent of the change in the objective function value.     

Minimizing total tardiness on a single machine with unequal release dates

This study addresses the problem of minimizing total tardiness on a single machine with unequal release dates. Dominance properties established in previous literatures and herein are adopted to develop branch and bound and heuristic procedures. Computational experiments were conducted to evaluate the approaches. The results revealed that the branch and bound algorithm is efficient in solving hard problems and easy problems that involve up to 50 and 500 jobs, respectively. The computational effectiveness of the heuristic is also reported.     

带有固定区间的单机双代理可中断总误工问题

研究带有固定区间的两个代理单机排序问题.第一个代理工件可中断,且工件到达时间与工期满足一致关系,目标函数为最小化总误工.第二个代理工件被安排在固定时间窗口.目标是寻找一个排序,使得满足第二个代理目标可行情况下,第一个代理目标函数值最小.在固定区间等于加工时间的情况下,利用分块原则,提出了一个伪多项式时间动态规划算法,并给出了固定区间大于加工时间情况下的时间复杂度分析.     

单机排序中带可分配工期的总误工问题的应急管理

对于机器排序的应急管理问题,Qi Xiang-tong等人进行了系统分析,得出了较好的结果.此文则考虑带可分配工期的总误工问题的应急管理问题.对于不同模型,或给出其最优序,或给出其近似解.