Common due window size and location determination in a single machine scheduling problem
- PDF / 164,279 Bytes
- 4 Pages / 595 x 842 pts (A4) Page_size
- 52 Downloads / 180 Views
#1998 Operational Research Society Ltd. All rights reserved. 0160-5682/98 $12.00 http://www.stockton-press.co.uk/jor
Common due window size and location determination in a single machine scheduling problem SD Liman1 SS Panwalkar1 and S Thongmee2 1
Texas Tech University and 2i2 Technologies, Inc., USA
We consider a single machine static and deterministic scheduling problem in which jobs have a common due window. Jobs completed within the window incur no penalties, other jobs incur either earliness or tardiness penalties. The objective is to ®nd the optimal size and location of the window as well as an optimal sequence to minimise a cost function based on earliness, tardiness, window size, and window location. We propose an O
n log n algorithm to solve the problem. Keywords: scheduling; sequencing; earliness±tardiness; just-in-time; due window
Introduction In this paper, we consider the single-machine non-preemptive earliness±tardiness scheduling problem with a common due window. All jobs are assumed to be simultaneously available at time zero and all parameters are known a priori. Jobs completed within the window incur no penalties, other jobs incur either earliness or tardiness penalties. The objective is to ®nd the optimal size and location of the window as well as an optimal sequence to minimise a cost function based on earliness, tardiness, window size, and window location. This penalty is consistent with the just-intime (JIT) concept that discourages tardiness as well as earliness. A polynomial algorithm is proposed in the paper. Numerous articles related to the concept of earliness± tardiness penalties have been published. The reader is referred to Raghavachari1 and Baker and Scudder2 for excellent comprehensive reviews of the earliness±tardiness problems. This paper extends works that have been done in the earliness±tardiness scheduling area (Kanet,3 Panwalkar et al,4 Anger et al,5 Hall,6 Cheng,7 Hall and Posner,8 Hall et al,9 Lee,10 KraÈmer and Lee,11,12 Liman and Ramaswamy,13 Liman et al,14 and Thongmee and Liman,15 among others). The majority assumed the existence of a common due date, we relax this assumption by allowing tolerances around the due date. Speci®cally, a common due window is assumed, a common due window is de®ned as a time interval speci®ed by a due date and a window width. A job, if completed within the due window, incurs no penalties. If it is ®nished before the due date, an earliness penalty is assessed. On the other hand, if it is completed after the window, a tardiness penalty is incurred. In this paper, the Correspondence: Dr SD Liman, Department of Industrial Engineering, Texas Tech University, Lubbock, TX 79409, USA.
due date and the window width are to be determined. This problem is important for cases where companies are responsible for quoting the due date and the window width to their customers. Both variables are penalised at costs that represent the industries' competitiveness. Problem formulation Let N denote a set of n jobs, all available for processing at time zero. Let
Data Loading...
