Abstract
The multiple Checkpoint Ordering Problem (mCOP) aims to find an optimal arrangement of n one-dimensional departments with given lengths such that the total weighted sum of their distances to m given checkpoints is minimized. In this paper we suggest an integer linear programming (ILP) approach and a dynamic programming (DP) algorithm, which is only exact for one checkpoint, for solving the mCOP. Our computational experiments show that there is no clear winner between the two methods. While the ILP approach is hardly influenced by increasing the number of checkpoints or the length of the departments, the performance of our DP algorithm deteriorates in both cases.
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
Eilon, S., & Chowdhury, I. G. (1977). Minimising waiting time variance in the single machine problem. Management Science, 23(6), 567–575.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In P. L. Hammer, E. L. Johnson, & B. H. Korte (Eds.), Discrete optimization II (Vol. 5, pp. 287–326). Annals of discrete mathematics. Amsterdam: Elsevier.
Hungerländer, P. (2017). The checkpoint ordering problem. Optimization, 1–14.
Queyranne, M., & Schulz, A. S. (2004). Polyhedral approaches to machine scheduling. Technical report.
Rothkopf, M. H. (1966). Scheduling independent tasks on parallel processors. Management Science, 12(5), 437–447.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Hungerländer, P., Maier, K. (2018). The Multiple Checkpoint Ordering Problem. In: Kliewer, N., Ehmke, J., Borndörfer, R. (eds) Operations Research Proceedings 2017. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-319-89920-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-89920-6_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-89919-0
Online ISBN: 978-3-319-89920-6
eBook Packages: Business and ManagementBusiness and Management (R0)