Abstract
In this paper, we consider a single machine scheduling problem in which processing a job will incur some cost which is relevant with the time slots occupied by the job. The objective is to minimize the makespan plus the total time slot costs. We prove that the problem is strongly NP-hard and analyze a special case with nonincreasing time slot costs.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Wan, G., Qi, X.: Scheduling with variable time slot costs. Naval Research Logistics 57, 159–171 (2010)
Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. Freeman, San Francisco (1979)
Lee, C.-Y.: Machine scheduling with availability constraints. In: Leung, J.Y.-T. (ed.) Handbook of scheduling: Algorithms, Models and Performance Analysis. ch. 22. CRC Press, Boca Raton (2004)
Lee, C.-Y., Liman, S.D.: Single-machine flow-time scheduling with scheduled maintenance. Acta Inform 29, 375–382 (1992)
Schmidt, G.: Scheduling with limited machine availability. Eur. J. Oper. Res. 121, 1–15 (2000)
Biskup, D.: A state-of-the-art review on scheduling with learning effects. Eur. J. Oper. Res. 188, 315–329 (2008)
Cheng, T.C.E., Ding, Q., Lin, B.M.T.: A concise survey of scheduling with time-dependent processing times. Eur. J. Oper. Res. 152, 1–13 (2004)
Janiak, A., Rudek, R.: The learning effect: Getting to the core of the problem. Inform. Process Lett. 103, 183–187 (2007)
Lin, B.M.T.: Complexity results for single-machine scheduling with positional learning effects. J. Oper. Res. Soc. 58, 1099–1102 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag GmbH Berlin Heidelberg
About this chapter
Cite this chapter
Zhong, W., Liu, X. (2012). A Single Machine Scheduling Problem with Time Slot Costs. In: Qian, Z., Cao, L., Su, W., Wang, T., Yang, H. (eds) Recent Advances in Computer Science and Information Engineering. Lecture Notes in Electrical Engineering, vol 126. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25766-7_90
Download citation
DOI: https://doi.org/10.1007/978-3-642-25766-7_90
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25765-0
Online ISBN: 978-3-642-25766-7
eBook Packages: EngineeringEngineering (R0)