Abstract
The paper deals with two problems of scheduling jobs on identical parallel machines, in which a due interval should be assigned to each job. Due interval is a generalization of well known classical due date and describes a time interval, in which a job should be finished. In the first problem, we have to find a schedule of jobs and a common due interval such that the sum of the total tardiness, the total earliness and due interval parameters is minimized. The second problem is to find a schedule of jobs and an assignment of due interval to all jobs, which minimize the maximum of the following three parts: the maximum tardiness, the maximum earliness and the due int erval parameters. We proved that the considered problems are NP-hard and outlined some methods how to solve them approximately as well as optimally.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cheng T.C.E., Gupta M.C. (1989). Survey of scheduling research involving due date determination decision. European Journal of Operational Research. 38, 156–166.
Chengbin C., Gordon V., Proth J.-M. (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.
Chengbin C., Gordon V., Proth J.-M. (2002). Due date assignment and scheduling: SLK, TWK and other due date assignment models. Production Planning & Control. 13, 117–132.
French S. (1982). Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. Horwood, Chichester.
Graham R.L. (1969). Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17 263–369.
Janiak A., Marek M. (2001). Multi-machine scheduling problem with optimal due interval assignment subject to generalized sum type criterion. Operations Research Procedings 2001. Springer, 207–212.
Liman S.D., Panwalkar S.S., Thongmee S. (1996). Determination of common due window location in a single machine scheduling problem. European Journal of Operational Research. 93, 68–74.
Liman S.D., Panwalkar S.S., 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.
Sahni S. (1976). Algorithm for scheduling indenpendent tasks. J. Assoc. Comput. Mach. 23, 116–127.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Janiak, A., Marek, M. (2003). Scheduling Problems with Optimal Due Interval Assignment Subject to Some Generalized Criteria. In: Leopold-Wildburger, U., Rendl, F., Wäscher, G. (eds) Operations Research Proceedings 2002. Operations Research Proceedings 2002, vol 2002. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-55537-4_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-55537-4_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00387-8
Online ISBN: 978-3-642-55537-4
eBook Packages: Springer Book Archive