Abstract
Traditional scheduling and due-date determination models assume that the production system is operating in a static and deterministic environment and that the system carries no workload at each scheduling epoch. In this research we consider a due-date determination model where the scheduler wishes to update the existing schedule when some new jobs have arrived into the system. In this model, jobs are categorized as either “old” or “new” jobs, where the due-dates of the old jobs are treated as given parameters and those of the new jobs are decision variables. The objective is to minimize the maximum weighted tardiness penalty and the due-date assignment cost. The computational complexity of this model is analyzed, and an efficient algorithm is developed for an important special case.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Cheng, T.C.E. and Gupta, M.C. (1989) Survey of scheduling research involving due-date determination decisions.European Journal of Operational Research, 38, 156-166.
Seidmann, A., Panwalkar, S.S. and Smith, M.L. (1981) Optimal assignment of due-dates for a single processor scheduling problem. International Journal of Production Research, 19, 393-399.
Seidmann, A. and Smith, M.L. (1981) Due-date assignment for production systems. Management Science, 27, 571-581.
Panwalkar, S.S., Smith, M.L. and Seidmann, A. (1982) Common due-date assignment to minimize total penalty for the one machine sequencing problem. Operations Research, 30, 391-399.
Hall, N.G. (1986) Scheduling problems with generalized due dates. IIE Transactions, 18, 220-222.
Cheng, T.C.E. and Kahlbacher, H.G. (1993) Single-machine scheduling to minimize earliness and number of tardy jobs. Journal of Optimization Theory and Applications, 77, 563-573.
Kahlbacher, H.G. and Cheng, T.C.E. (1993) Parallel-machine scheduling to minimize costs of earliness and number of tardy jobs. Discrete Applied Mathematics, 47, 139-164.
Raman, N., Talbot, F.B. and Rachamadugu, R.V. (1989) Due date based scheduling in a general flexible manufacturing system. Journal of Operations Management, 8, 115-132.
Church, L.K. and Uzsoy, R. (1992) Analysis of periodic and event-driven rescheduling policies in dynamic shops. International Journal of Computer Integrated Manufacturing, 5, 153-163.
Wu, S.D., Storer, R.H. and Chang, P.C. (1992) A rescheduling procedure for manufacturing systems under random disruptions, in New Directions for Operations Research in Manufacturing, Fandel, G., Gulledge, T. and Jones, A. (eds.), Springer, New York, pp. 292-308.
Wu, S.D., Storer, R.H. and Chang, P.C. (1993) One-machine rescheduling with eficiency and stability as criteria. Computers and Operations Research, 20, 1-14.
Unal, A.T., Uzsoy, R. and Kiran, A.S. (1997) Rescheduling on a single machine with part-type dependent setup times and deadlines. Annals of Operations Research, 70, 93-113.
Lawler, E.L. (1973) Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19, 544-546.
Du, J. and Leung, J.Y.-T. (1990) Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 15,483-495.
Jackson, J.R. (1955) Scheduling a production line to minimize maximum tardiness. Research Report 43, Management Science Research Project, University of California, Los Angeles.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Li, CL., Cheng, T.C.E. Due-date determination with resequencing. IIE Transactions 31, 183–188 (1999). https://doi.org/10.1023/A:1007550328128
Issue Date:
DOI: https://doi.org/10.1023/A:1007550328128