Abstract
In this paper we address the scheduling problem of unit processing time jobs on a single machine considering number of tardy jobs and a measure of earliness. We consider total absolute lateness, total earliness and maximum earliness, as earliness measures.
We provide a simple rule to solve the total earliness and maximum earliness problems in a unit execution time single machine environment.
Unit processing times allow for the formulation of the scheduling problem as an assignment problem. When there are two criteria the formulation includes side constraints. We formulate the problem and solve it to generate all efficient solutions. We provide computational results on a set of problems.
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.
References
Azizoglu, M., S. Kondakci, and Ö. Kirca: Bicriteria Scheduling Problem Involving Total Tardiness and Total Earliness Penalties. International Journal of Production Economics. 23 (1991) 17–24.
Chen, C.L. and R.L Bulfin: Scheduling Unit Processing Time Jobs on a Single Machine with Multiple Criteria. Computers and Operations Research. 17 (1990) 1–7.
De, P., J.B. Ghosh, and, C.E. Wells: Some Clarifications on the Bicriteria Scheduling of Unit Execution Time Jobs on a Single Machine. Computers and Operations Research. 18 (1991) 717–720.
Emmons, H.: One Machine Sequencing to Minimize Mean Flow Time with Minimum Tardy. Naval Research Logistics Quarterly. 22 (1975) 585–592.
Fisher, M.L.: A Dual Algorithm for the One-Machine Scheduling Problem. Mathematical Programming. 11 (1976) 229–251.
Kondakci, S., M. Azizoglu, and M. Köksalan: Note: Bicriteria Scheduling, Minimizing Flow time and Maximum Tardiness. Naval Research Logistics. (1995) (forthcoming).
Lin, K.S., Hybrid Algorithm for Sequencing with Bicriteria. Journal of Optimization Theory and Applications. (1983) 105–124.
Moore, J.M.: A n-job, One Machine Sequencing Algorithm for minimizing the Number of Late Jobs. Management Science. 15 (1968) 102–109.
Nelson, R.T., R.K. Sarin, and, R.L. Daniels: Scheduling with Multiple Performance Measures: The One Machine Case. Management Science. 32 (1986) 464–479.
Panwalkar, S.S., R.K. Dudek, and M.L. Smith: Sequencing Research and the Industrial Scheduling Problem. In S.E. Elmaghraby (ed): Symposium on the Theory of Scheduling and Its Application, Springer, NY 1973.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kondakci, S.K., Emre, E., Köksalan, M. (1997). Scheduling of Unit Processing Time Jobs on a Single Machine. In: Fandel, G., Gal, T. (eds) Multiple Criteria Decision Making. Lecture Notes in Economics and Mathematical Systems, vol 448. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-59132-7_70
Download citation
DOI: https://doi.org/10.1007/978-3-642-59132-7_70
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62097-6
Online ISBN: 978-3-642-59132-7
eBook Packages: Springer Book Archive