Insights into two solution procedures for the single machine tardiness problem
- PDF / 244,376 Bytes
- 7 Pages / 595 x 794 pts Page_size
- 111 Downloads / 180 Views
#2002 Operational Research Society Ltd. All rights reserved. 0160-5682/02 $15.00 www.palgrave-journals.com/jors
Insights into two solution procedures for the single machine tardiness problem JT Naidu1*, JND Gupta2 and B Alidaee3 1
Philadelphia University, Philadelphia, PA, USA; 2The University of Alabama in Huntsville, Huntsville, AL, USA; and 3University of Mississippi, Oxford Campus, MS, USA 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. Journal of the Operational Research Society (2002) 53, 800–806. doi:10.1057/palgrave.jors.2601384 Keywords: single machine scheduling; minimizing tardiness; optimal and heuristic decomposition; modified due date rule
Introduction Consider the following scenario: a set N ¼ f1; . . . ng of n jobs is available at time zero and requires processing on a single machine. Associated with each job i 2 N , are its processing time pi and due date di. A sequence giving the processing order of the jobs defines a schedule since there is no advantage in keeping the machine idle when there are jobs to be processed. If job i is completed after its due date, it is called tardy, otherwise it is considered early. Given a schedule s ¼ ðsð1Þ; . . . ; sðnÞÞ P of n jobs, the completion time of each job s(i), CsðiÞ ¼ is¼1 psðsÞ : The tardiness of job s(i), TsðiÞ ¼ maxfCsðiÞ dsðiÞ ; 0g: Then, the single machine total tardiness problem considered here consists of finding a schedule sP¼ ðsð1Þ; . . . ; sðnÞÞ such that the sum of job tardiness, ni¼1 TsðiÞ is minimum. Following the standard three-parameter notation of schedP uling problems, we designate this problem as a 1jj Ti problem P where 1 indicates that it is a single machine shop and Ti indicates that the objective is the minimization of P the sum of the tardiness of all n jobs. The 1jj Ti problem has been shown to be NP-hard in the ordinary sense by Du and Leung.1 Developments in solving this problem are reviewed by Koulamas.2 P The first thorough study of the 1jj Ti problem was done 3 by Emmons who proved three fundamental theorems that established the precedence relations among pairs that must be satisfied in at least one optimal schedule. Recently, Tansel and Sabuncuoglu4 investigated these theorems with *Correspondence: JT Naidu, School of Business Administration, Philadelphia University, School House Lane and Henry Avenue, Philadelphia, PA 19144, USA. E-mail: [email protected]
a geometric viewpoint for better insights into the dominance conditions. The most successful optimal solution procedure for this problem
Data Loading...
