Abstract
In due-date assignment problems with a common flow-allowance, the due-date of a given job is defined as the sum of its processing time and a job-independent constant. We study flow-allowance on a single machine, with an objective function of a minmax type. The total cost of a given job consists of its earliness/tardiness and its flow-allowance cost components. Thus, we seek the job schedule and flow-allowance value that minimize the largest cost among all the jobs. Three extensions are considered: the case of general position-dependent processing times, the model containing an explicit cost for the due-dates, and the setting of due-windows. Properties of optimal schedules are fully analysed in all cases, and all the problems are shown to have polynomial time solutions.
Similar content being viewed by others
References
Adamopoulos GI and Pappis CP (1996). Single machine scheduling with flow allowances. Journal of the Operational Research Society 47: 1280–1285.
Alidaee B (1991). Optimal assignment of slack due-date and sequencing in a single machine shop. Applied Mathematics Letters 4: 9–11.
Cheng TCE (1986). Optimal slack due-date determination and sequencing. Engineering Costs and Production Economics 10: 305–309.
Cheng TCE (1989). Optimal assignment of slack due-dates and sequencing in a single machine shop. Applied Mathematics Letters 2: 333–335.
Cheng TCE (1991). Optimal constant due date determination and sequencing of n jobs on a single machine. International Journal of Production Economics 22: 259–261.
Cheng TCE, Oguz C and Qi XD (1996). Due-date assignment and single machine scheduling with compressible processing times. International Journal of Production Economics 43: 107–113.
De P, Ghosh JB and Wells CE (1994). Solving a generalized model for CON due date assignment and sequencing. International Journal of Production Economics 34: 179–185.
Dyer ME (1984). Linear time algorithms for two- and three-variable linear programs. SIAM Journal on Computing 13: 31–45.
Gordon VS (1993). A note on optimal assignment of slack due-dates in single-machine scheduling. European Journal of Operational Research 70: 311–315.
Gordon VS, Proth J-M and Chu C (2002). A survey of the state-of-the-art of common due date assignment and scheduling research. European Journal of Operational Research 139: 1–25.
Karacapilidis NI and Pappis CP (1993). Optimal due-date determination and sequencing of n jobs on a single machine using the SLK method. Computers in Industry 21: 335–339.
Liman SD, Panwalker SS and Thongmee S (1998). Common due window size and location determination in a single machine scheduling problem. Journal of the Operational Research Society 49: 1007–1010.
Mosheiov G and Oron D (2007). Minmax scheduling with job-classes and earliness-tardiness costs. European Journal of Operational Research 177: 612–622.
Mosheiov G and Oron D (2010). Job dependent due-window assignment based on a common flow allowance. Foundations of Computing and Decision Sciences 35: 185–195.
Mosheiov G and Sarig A (2009). Minmax scheduling problems with a common due-window. Computers & Operations Research 36: 1886–1892.
Oğuz C and Dincer C (1994). Single machine earliness-tardiness scheduling problems using the equal-slack rule. Journal of the Operational Research Society 45: 589–594.
Quaddus MA (1990). A network flow approach to optimal slack due-date determination. Engineering Costs and Production Economics 18: 265–267.
Seidmann A, Panwalkar SS and Smith ML (1981). Optimal assignment of due-dates for a single processor scheduling problem. International Journal of Production Research 19: 393–399.
Shabtay D and Steiner G (2007). Optimal due date assignment and resource allocation to minimize the weighted number of tardy jobs on a single machine. Manufacturing & Service Operations Management 9: 332–350.
Wang J-B (2006). Single machine common flow allowance scheduling with controllable processing times. Journal of Applied Mathematics and Computing 21: 249–257.
Wang X-Y and Wang M-Z (2010). Single machine common flow allowance scheduling with a rate-modifying activity. Computers & Industrial Engineering 59: 898–902.
Acknowledgements
This paper was supported by The Recanati Fund and the Charles Rosen Chair of Management, The School of Business Administration, The Hebrew University, Jerusalem, Israel.
Author information
Authors and Affiliations
Appendix
Appendix
Proofs of Lemmas 1–3 (Property 8)
Consider an optimal schedule S 1 in which (l) and (k) are the indices of two consecutive jobs, such that P (l)>P (k). Assume that job (l) starts at time t. We create a new schedule S 2 by replacing jobs (l) and (k).
Lemma 1:
-
An optimal schedule exists in which the early jobs are scheduled according to SPT.
Proof:
-
Assume that jobs (l) and (k) in S 1 are early, thus their costs (in S 1) are:
The costs of jobs (k) and (l) in sequence S 2 are:
Since P (l)>P (k) and α>0:
Thus, schedule S 1 is not optimal (and the early jobs must be scheduled according to SPT). □
Lemma 2:
-
An optimal schedule exists in which the tardy jobs are scheduled according to SPT.
Proof:
-
Assume that jobs l and k are tardy, and thus their costs in the sequence S 1 are:
The costs of jobs (k) and (l) in S 2 are:
Again, since P (l)>P (k) and β⩾γ>0:
implying that schedule S 1 is not optimal (and the tardy jobs must be scheduled according to SPT as well). □
Lemma 3:
-
An optimal schedule exists in which the processing time of the last early job is not larger than that of the first tardy job.
Proof:
-
In the sequence S 1, let (l) be the last early job (which starts at time t), and the following job (k) is the first tardy job. The costs of these jobs in S 1 are:
As before, we assume P (l)>P (k), and schedule S 2 is obtained by replacing jobs (k) and (l). There are three sub-cases regarding the status of jobs (k) and (l) in the sequence S 2:
- Sub-case 1::
-
In S 2 job (k) is early and job (l) is tardy:
It is easily verified (since P (l)>P (k) and β⩾γ>0) that (A.3)<(A.1) and (A.4)⩽(A.2).
- Sub-case 2::
-
In S 2 both jobs (k) and (l) are early:
Here, (A.5)<(A.1) and (A.6)<(A.1).
- Sub-case 3::
-
In S 2 both jobs (k) and (l) are tardy:
In this case (A.7)<(A.2) and (A.8)⩽(A.2).
In all three sub-cases, S 1 is shown to be non-optimal, implying that an optimal schedule exists in which the processing time of the last early job is never larger than that of the first tardy job. □
Rights and permissions
About this article
Cite this article
Mor, B., Mosheiov, G. Minmax scheduling problems with common flow-allowance. J Oper Res Soc 63, 1284–1293 (2012). https://doi.org/10.1057/jors.2011.135
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2011.135