A new decomposition approach for the single machine total tardiness scheduling problem
- PDF / 186,970 Bytes
- 6 Pages / 595 x 842 pts (A4) Page_size
- 99 Downloads / 206 Views
#1998 Operational Research Society Ltd. All rights reserved. 0160-5682/98 $12.00 http://www.stockton-press.co.uk/jor
A new decomposition approach for the single machine total tardiness scheduling problem F Della Croce, R Tadei, P Baracco, and A Grosso D.A.I., Politecnico di Torino, Italy 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. Keywords: scheduling; total tardiness; decomposition; lower bound
Introduction
Main result and its implications
This paper considers the well P known n-job single machine total tardiness problem 1k nj1 Tj , which is NP-hard in the ordinary sense.1 For a comprehensive survey we refer to Koulamas.2 The main theoretical ®ndings for this problem are Emmons' dominance conditions3 and Lawler's decomposition rule4 which was established for a slightly more general objective function (total weighted tardiness with `agreeable' weights). Emmons' conditions establish precedence relations among jobs in an optimal sequence. Lawler's decomposition rule allows to decompose a problem into subproblems given the position of the largest processing time job in an optimal sequence. A further result by Lawler4 shows a property which reduces the list of possible positions of the largest processing time job in an optimal sequence. Potts and Van Wassenhove5 and then Szwarc6 improved this result by further reducing that list. Szwarc and Mukhopadhyay7 recently proposed a branch and bound procedure applying a powerful Split Rule strongly based on the ®ndings of Emmons,3 Potts and Van Wassenhove5 and Szwarc.6 The authors report computational tests on problems with up to 150 jobs in size. In this paper a new partition theorem based on Emmons' conditions is given. This theorem generalises Lawler's decomposition rule. From this theorem, a new decomposition rule applied to the smallest due date job is derived and a double decomposition procedure is developed. A new lower bound based on due dates reassignment is presented. A branch and bound method embedding the double decomposition and the lower bound is tested on problems with size up to 150 jobs.
Let J {1, 2, . . . , n} be a set of n jobs and pj, dj, Cj and Tj max{0, Cj 7 dj} the processing time, the due date, the completion time and the tardiness of job j respectively. Let S be a schedule of n jobs. Let ri, s and p be subsequences of S. The one-machine n-job total tardiness problem may be stated P as follows. Find a schedule S that minimises f
S nj1 Tj where the jobs are assumed to be processed without pre-emption, from time zero, on a single machine that can handle only one job at a time. For a given job i, let Bi and Ai be the subsets of jobs that, at any point, have
Data Loading...
