Abstract
We consider the problem of scheduling on uniform processors which may not start processing at the same time with the purpose of minimizing the maximum completion time. We provide a variant of the MULTIFIT algorithm which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and within \(\sqrt{6}/2\) times the optimal maximum completion time for problem instances with two processors. Experimental results suggest that our algorithm is a viable option for addressing this problem in practice.
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
Similar content being viewed by others
References
Coffman Jr., E.G., Garey, M.R., Johnson, D.S.: An application of Bin-Packing to multiprocessor scheduling. SIAM J. Comput. 7(1), 1–17 (1978)
Lee, C.Y.: Parallel Machine Scheduling with nonsimultaneous machine available time. Discrete Appl. Math. 30(1), 53–61 (1991)
Chang, S.Y., Hwang, H.: The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines. Discrete Appl. Math. 92, 135–147 (1999)
Hwang, H.C., Lim, K.: Discrete Appl. Math. 167, 172–187 (2014)
Friesen, D.K., Langston, M.A.: Bounds for multifit scheduling on uniform processors. SIAM J. Comput. 12(1), 60–69 (1983)
Chen, B.: Tighter bound for MULTIFIT scheduling on uniform processors. Discrete Appl. Math. 31(3), 227–260 (1991)
Burkard, R.E., He, Y.: A note on MULTIFIT scheduling for uniform machines. Computing 61(3), 277–283 (1998)
He, Y.: Uniform machine scheduling with machine available constraints. Acta Math. Appl. Sin. (English Series), 16(2), 122–129 (2000)
Grigoriu, L., Friesen, D.K.: Approximation for scheduling on uniform nonsimultaneous parallel machines. J. Sched. (2016). doi:10.1007/s10951-016-0501-1
Grigoriu, L., Friesen, D.K.: Scheduling on uniform processors with at most one downtime on each machine. Discrete Optim. 17, 14–24 (2015)
Grigoriu, L.: Scheduling on parallel machines with variable availability patterns. Ph.D. thesis, Politehnica University Bucharest (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Grigoriu, L., Friesen, D.K. (2018). Scheduling on Uniform Nonsimultaneous Parallel Machines. In: Fink, A., Fügenschuh, A., Geiger, M. (eds) Operations Research Proceedings 2016. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-319-55702-1_62
Download citation
DOI: https://doi.org/10.1007/978-3-319-55702-1_62
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-55701-4
Online ISBN: 978-3-319-55702-1
eBook Packages: Business and ManagementBusiness and Management (R0)