Abstract
We consider a scheduling problem with reconfigurable resources. Several types of jobs have to be processed by a set of identical resources (e.g. robots, workers, processors) over a discrete time horizon. In each time period, teams of resources must be formed to process jobs. During a given time period, a team handles one type of job and the number of jobs that can be processed depends on the team size. A resource which is used to perform some job type in a given period may be employed for another job type in the next period. The objective is to determine the minimum number of resources needed to meet a given demand for each job type. We provide a polynomial-time 4/3-approximation algorithm for this strongly NP-hard problem.
This work was financed by the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20–25) and by the Auvergne-Rhone-Alpes region under the program “Pack Ambition Recherche”. It was also supported by the International Research Center “Innovation Transportation and Production Systems” of the I-SITE CAP 20–25 and by Institut Carnot M.I.N.E.S.
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
Notes
- 1.
In the classic IMS syntax, “boxes” are typically called machines and the “items” are jobs with a certain processing time. We modify this syntax to be consistent with the Multi_Bot framework.
References
Battaïa, O., et al.: Workforce minimization for a mixed-model assembly line in the automotive industry. Int. J. Prod. Econ. 170, 489–500 (2015)
Beşikci, U., Bilge, U., Ulusoy, G.: Multi-mode resource constrained multi-project scheduling and resource portfolio problem. Eur. J. Oper. Res. 240(1), 22–31 (2015)
Boysen, N., Schulze, P., Scholl, A.: Assembly line balancing: what happened in the last fifteen years? Eur. J. Oper. Res. 301(3), 797–814 (2022)
Brinkop, H., Jansen, K.: High multiplicity scheduling on uniform machines in FPT-time. CoRR abs/2203.01741 (2022)
Chaikovskaia, M.: Optimization of a fleet of reconfigurable robots for logistics warehouses. Ph.D. thesis, Université Clermont Auvergne, France (2023)
Chaikovskaia, M., Gayon, J.P., Marjollet, M.: Sizing of a fleet of cooperative and reconfigurable robots for the transport of heterogeneous loads. In: Proceedings of IEEE CASE, pp. 2253–2258 (2022)
Coffman, E.G., Jr., Garey, M.R., Johnson, D.S.: An application of bin-packing to multiprocessor scheduling. SIAM J. Comput. 7(1), 1–17 (1978)
Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416–429 (1969). https://doi.org/10.1137/0117039
Hartmann, S., Briskorn, D.: An updated survey of variants and extensions of the resource-constrained project scheduling problem. Eur. J. Oper. Res. 297(1), 1–14 (2022)
Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. In: FOCS, pp. 79–89 (1985)
McCormick, S.T., Smallwood, S.R., Spieksma, F.: A polynomial algorithm for multiprocessor scheduling with two job lengths. Math. Oper. Res. 26(1), 31–49 (2001)
MecaBotiX (2023). https://www.mecabotix.com/
Mnich, M., Wiese, A.: Scheduling and fixed-parameter tractability. Math. Program. 154(1–2), 533–562 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bergé, P., Chaikovskaia, M., Gayon, JP., Quilliot, A. (2024). Approximation Algorithm for Job Scheduling with Reconfigurable Resources. In: Basu, A., Mahjoub, A.R., Salazar González, J.J. (eds) Combinatorial Optimization. ISCO 2024. Lecture Notes in Computer Science, vol 14594. Springer, Cham. https://doi.org/10.1007/978-3-031-60924-4_20
Download citation
DOI: https://doi.org/10.1007/978-3-031-60924-4_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-60923-7
Online ISBN: 978-3-031-60924-4
eBook Packages: Computer ScienceComputer Science (R0)