Abstract
We investigate a combined approach for job scheduling on parallel machines and the location of machines referred to in the literature as ScheLoc. We sum up the up-to-date achievements and propose a general classification of such a two-part problem involving different solving methods. A sequential approach requires both parts’ successive consideration, unlike the joint proposal with their simultaneous investigation. The uncertain version is also proposed, aiming to replace the two-part deterministic problem with a single counterpart with interval release dates of jobs. The mentioned solution approaches are illustrated by specific job scheduling and machine location sub-problems.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Józefczyk, J., Hojda, M.: Systems approach in complex problems of decision-making and decision-support. In: Kulczycki, P., Korbicz, J., Kacprzyk, J. (eds.) Automatic Control, Robotics, and Information Processing. SSDC, vol. 296, pp. 589–615. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-48587-0_19
Nagy, G., Salhi, S.: Location-routing: issues, models and methods. Eur. J. Oper. Res. 177, 649–672 (2007)
Hennes H., Hamacher H.W.: Integrated Scheduling and Location Models: Single Machine Makespan Problems. Report on Wirtschaftsmathematik, p. 82, University of Kaiserslautern (2002)
Elvikis, D., Hamacher, H.W., Kalsch M.T.: Simultaneous scheduling and location (ScheLoc): the planar ScheLoc makespan problem. J. Sched. 12(4), 361–374 (2009)
Hessler, C.J.: Scheduling-Location Algorithms with Applications in Evacuation Planning. Verlag Dr, Hut (2017)
Pinedo, M.L.: Scheduling: Theory. Algorithms. and Systems. Springer-Verlag, New York (2012). https://doi.org/10.1007/978-1-4614-2361-4
Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy, Kan A., H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979)
Kalsch, M.T., Drezner, Z.: Solving scheduling and location problems in the plane simultaneously. Comput. Oper. Res. 37(2), 256–264 (2010)
Drezner, Z., Suzuki, A.: The big triangle small triangle method for the solution of nonconvex facility location problems. Oper. Res. 52(1), 128–135 (2004)
Hessler, C.J., Deghdak, K.: Discrete parallel machine makespan ScheLoc problem. J. Comb. Optim. 34(4), 1159–1186 (2017)
Ławrynowicz, M., Józefczyk J.: A memetic algorithm for the discrete scheduling-location problem with unrelated executors. In: Proceedings of the 24th International Conference on Methods and Models in Automation and Robotics MMAR. Międzyzdroje. Poland, 26–29 August 2019
Piasecki, B.: Application of AI-based algorithms for joint problem of task scheduling and deployment of executors Master Thesis. Wroclaw University of Science and Technology. Poland (2018). (in Polish)
Piasecki, B., Józefczyk, J.: Evolutionary algorithm for joint task scheduling and deployment of executors. In: Automation of Discrete Processes. Theory and Applications Silesian University of Technology, vol. 1, pp. 169–178 (2018). (in Polish)
Rajabzadeh, M., Ziaee, M., Bozorgi-Amiri, A.: Integrated approach in solving parallel machine scheduling and location (ScheLoc) problem. Int. J. Ind. Eng. Comput. 7(4), 573–584 (2016)
Filcek, G., Józefczyk, J., Ławrynowicz, M.: An evolutionary algorithm for joint bi-criteria location-scheduling problem. Int. J. Ind. Eng. Comput. 12, 159–176 (2021)
Deb, K.: Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley & Sons, Chichester (2001)
Wesolkowski, S., Francetic, N., Grant, S.C.: Trade training device selection via multi-objective optimization. In: IEEE Congress on Evolutionary Computation (2014)
Kalai, R., Lamboray, C., Vanderpooten, D.: Lexicographic a-robustness: An alternative to min-max criteria. Euro. J. Oper. Res. 220(3), 722–728 (2020)
Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P.: Complexity of machine scheduling problems. Ann. Discrete Math. 1, 343–362 (1977)
Garey, M.R., Johnson, D.S.: Computers and Intractability A Guide to the Theory of NP-Completeness. , W. H. Freeman and Company, New York (1979)
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, London (2013)
Liu, M., Liu, X., Zhang, E., Chu, F., Chu, Ch.: Scenario-based heuristic to two-stage stochastic program for the parallel machine ScheLoc problem. Int. J. Prod. Res. 57(6), 1706–1723 (2019)
Kouvelis, P., Yu, G.: Robust Discrete Optimization and Its Applications. Kluwer Academic Publishers, London .(1997)
Rosing, K.E., Revelle, C.S., Schilling, D.A.: A gamma heuristic for the p-median problem. Eur. J. Oper. Res. 117(3), 522–532 (1999)
Lin, Y.K.: Particle swarm optimization algorithm for unrelated parallel machine scheduling with release dates, Math. Probl. Eng, 2013, 409486 (2013)
Bachtler, O., Krumke, S.O., Le, H.M.: Robust single machine makespan scheduling with release date uncertainty. Oper. Res. Lett. 48, 816–819 (2020)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Józefczyk, J., Ławrynowicz, M., Filcek, G. (2022). On Problems and Methods of Coordinated Scheduling and Location. In: Atanassov, K.T., et al. Uncertainty and Imprecision in Decision Making and Decision Support: New Advances, Challenges, and Perspectives. IWIFSGN BOS/SOR 2020 2020. Lecture Notes in Networks and Systems, vol 338. Springer, Cham. https://doi.org/10.1007/978-3-030-95929-6_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-95929-6_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-95928-9
Online ISBN: 978-3-030-95929-6
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)