Abstract
The goal of this paper is to propose algorithms for scheduling problem, where set of jobs performed on a single processor. Each job has a release time, when it becomes available for processing, a processing time and a delivery time. We study the case in which there exist precedence constrains among jobs and preemption is not allowed. The objective is to minimize the time, by which all jobs are delivered. The single machine scheduling problem is one of the classic NP-hard optimization problems, and it is useful in solving flowshop and jobshop scheduling problems. We develop branch and bound algorithm for the problem. We propose an approximation algorithm to find an upper bound, solve the preemptive version of the problem to provide a lower bound and use a binary branching rule, where at each branch node, a complete schedule is generated.
To illustrate the effectiveness of our algorithms we tested them on randomly generated set of jobs.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Artigues, C., Feillet, D.: A branch and bound method for the job-shop problem with sequence-dependent setup times. Ann. Oper. Res. 159, 135–159 (2008)
Baker, K., Lawner, E., Lenstra, J., Rinnooy Kan, A.: Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constrains. Oper. Res. 31, 381–386 (1983)
Baker, K., Su, Z.: Sequensing with due-dates and early start times to minimize maximum tardiness. Naval Res. Logist. Q. 21, 171–176 (1974)
Brucker, P.: Scheduling Algorithms, 5th edn. Springer, Berlin (2007)
Carlier, J.: The one machine sequencing problem. Eur. J. Oper. Res. 11, 42–47 (1982)
Chandra, C., Liu, Z., He, J., Ruohonen, T.: A binary branch and bound algorithm to minimize maximum scheduling cost. Omega 42, 9–15 (2014)
Grabowski, J., Nowicki, E., Zdrzalka, S.: A block approach for single-mashine scheduling with release dates and due dates. Eur. J. Oper. Res. 26, 278–285 (1986)
Graham, R., Lawner, E., Rinnoy Kan, A.: Optimization and approximation in deterministic sequencing and scheduling. A survey. Ann. Discret. Math. 5(10), 287–326 (1979)
Grigoreva, N.: Branch and bound method for scheduling precedence constrained tasks on parallel identical processors. In: Proceedings of The World Congress on Engineering 2014, WCE 2014. Lecture Notes in Engineering and Computer Science, pp. 832–836, London, U.K. (2014)
Grigoreva, N.: Branch and bound algorithm for the single machine scheduling problem with release and delivery times. In: 2018 IX International Conference on Optimization and Applications (OPTIMA2018) Supplementory Volume, Petrovac, Montenegro, 1–5 October 2018 (2018)
Hall, L., Posner, M.: Generating experimental data forcomputation testing with machine scheduling applications. Oper. Res. 49, 854–865 (2001)
Kanet, J., Sridharan, V.: Scheduling with inserted idle time:problem taxonomy and literature review. Oper. Res. 48(1), 99–110 (2000)
Lenstra, J., Rinnooy Kan, A., Brucker, P.: Complexity of machine scheduling problems. Ann. Discret. Math. 1, 343–362 (1977)
Liu, Z.: Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints. Comput. Oper. Res. 37, 1537–1543 (2010)
McMahon, G., Florian, N.: On scheduling with ready times and due dates to minimize maximum lateness. Oper. Res. 23(3), 475–482 (1975)
Nowicki, E., Smutnicki, C.: An approximation algorithm for a single-machine scheduling problem with release times and delivery times. Discret. Appl. Math. 48, 69–79 (1994)
Pan, Y., Shi, L.: Branch and bound algorithm for solving hard instances of the one-mashine sequencing problem. Eur. J. Oper. Res. 168, 1030–1039 (2006)
Potts, C.: Analysis of a heuristic for one machine sequencing with release dates and delivery times. Oper. Res. 28(6), 445–462 (1980)
Schage, L.: Obtaining optimal solutionto resourse constrained network scheduling problems. Unpublished manuscript (1971)
Sourirajan, K., Uzsoy, R.: Hybrid decomposition heuristics for solving large-scale scheduling problems in semiconductor wafer fabrication. J. Sched. 10, 41–65 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Grigoreva, N. (2020). Single Machine Scheduling with Precedence Constrains, Release and Delivery Times. In: Wilimowska, Z., Borzemski, L., Świątek, J. (eds) Information Systems Architecture and Technology: Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology – ISAT 2019. ISAT 2019. Advances in Intelligent Systems and Computing, vol 1052. Springer, Cham. https://doi.org/10.1007/978-3-030-30443-0_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-30443-0_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-30442-3
Online ISBN: 978-3-030-30443-0
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)