New insights on the single machine total tardiness problem
- PDF / 144,251 Bytes
- 8 Pages / 596 x 842 pts (A4) Page_size
- 39 Downloads / 171 Views
#1997 Operational Research Society Ltd. All rights reserved. 0160-5682/97 $12.00
New insights on the single machine total tardiness problem B C Tansel and I Sabuncuoglu Bilkent University, Turkey 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. Keywords: single machine scheduling; tardiness
Introduction In this paper, we analyze the total tardiness scheduling problem and identify some easy and hard instances using a geometric viewpoint. A single machine is to process n jobs with known processing times and due dates. Ready times are zero. Tardiness is the positive lateness a job incurs if it is completed after its due date and the object is to sequence the jobs to minimize the total tardiness. In the weighted case, each job’s tardiness is multiplied by a positive weight. The weighted tardiness problem is NP-hard in the strong sense (Lenstra et al1) and the unweighted case is NP-hard in the ordinary sense (Du and Leung2). The first thorough study of the problem was done by Emmons3 in 1969. Emmons proved three fundamental theorems that helped establish precedence relations among job pairs that must be satisfied in at least one optimal schedule. These are generalized to arbitrary nondecreasing cost functions by Rinnooy Kan et al 4. As Emmons’ theorems have become widely known, most of the research on optimizing algorithms have used Emmons’ theorems to first establish job precedences followed by some form of implicit enumeration (for example Fisher5, and Schrage and Baker6). In general, dynamic programming (DP) algorithms seem to be more efficient than branch and bound algorithms (Baker and Schrage7). One drawback of DP is its O(2n) storage requirements which renders it impractical for large problems. In this context, Sen, Austin, and Ghandforoush8 proposed a more efficient implicit enumeration technique which is not based on Emmons’ theorems. They compared their branching algorithm with the DP approach of Schrage and Baker and found that the proposed method requires less storage space. Recently, Sen and Borah9 proposed a new branching algorithm based on theorems some of which are corollaries to Rinnooy Kan et al 4. Their algorithm is Correspondence: BC Tansel, Department of Industrial Engineering, Bilkent University, 06533 Bilkent, Ankara, Turkey.
effective in reducing the problem size by providing a smaller set of candidate sequences. A fundamentally different line of theory, decomposition, was first developed by Lawler10. Decomposition theory focuses on relations between jobs and positions in a sequence rather than job pairs. Lawler10 gave a pseudopolynomial dynamic programming algorithm that relies on a repeated use of his de
Data Loading...
