Non-preemptive Scheduling on Machines with Setup Times
A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, in: F. Dehne, J.R. Sack, U. Stege (Eds.), Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, 2015, pp. 542--553.
Download
274-chp_3A10.1007_2F978-3-319-21840-3_45.pdf
215.50 KB
Conference Paper
Author
Mäcker, AlexanderLibreCat;
Malatyali, Manuel;
Meyer auf der Heide, FriedhelmLibreCat;
Riechers, Sören
Editor
Dehne, Frank;
Sack, Jörg Rüdiger;
Stege, Ulrike
Abstract
Consider the problem in which n jobs that are classified into k types are to be scheduled on m identical machines without preemption. A machine requires a proper setup taking s time units before processing jobs of a given type. The objective is to minimize the makespan of the resulting schedule. We design and analyze an approximation algorithm that runs in time polynomial in n,m and k and computes a solution with an approximation factor that can be made arbitrarily close to 3/2.
Publishing Year
Proceedings Title
Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings
forms.conference.field.series_title_volume.label
Lecture Notes in Computer Science
Page
542--553
LibreCat-ID
Cite this
Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Non-preemptive Scheduling on Machines with Setup Times. In: Dehne F, Sack JR, Stege U, eds. Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings. Lecture Notes in Computer Science. ; 2015:542--553. doi:10.1007/978-3-319-21840-3_45
Mäcker, A., Malatyali, M., Meyer auf der Heide, F., & Riechers, S. (2015). Non-preemptive Scheduling on Machines with Setup Times. In F. Dehne, J. R. Sack, & U. Stege (Eds.), Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings (pp. 542--553). https://doi.org/10.1007/978-3-319-21840-3_45
@inproceedings{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2015, series={Lecture Notes in Computer Science}, title={Non-preemptive Scheduling on Machines with Setup Times}, DOI={10.1007/978-3-319-21840-3_45}, booktitle={Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings}, author={Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}, editor={Dehne, Frank and Sack, Jörg Rüdiger and Stege, UlrikeEditors}, year={2015}, pages={542--553}, collection={Lecture Notes in Computer Science} }
Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and Sören Riechers. “Non-Preemptive Scheduling on Machines with Setup Times.” In Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, edited by Frank Dehne, Jörg Rüdiger Sack, and Ulrike Stege, 542--553. Lecture Notes in Computer Science, 2015. https://doi.org/10.1007/978-3-319-21840-3_45.
A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Non-preemptive Scheduling on Machines with Setup Times,” in Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, 2015, pp. 542--553.
Mäcker, Alexander, et al. “Non-Preemptive Scheduling on Machines with Setup Times.” Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, edited by Frank Dehne et al., 2015, pp. 542--553, doi:10.1007/978-3-319-21840-3_45.
Main File(s)
File Name
274-chp_3A10.1007_2F978-3-319-21840-3_45.pdf
215.50 KB
Access Level
Closed Access
Last Uploaded
2018-03-21T09:28:34Z
Google Scholar