Abstract
In this paper we study the Parallel machine scheduling problem with Two Servers in the Restrictive case (PTSR). Before its processing, the job must be loaded on a common loading server. After a machine completes processing one job, an unloading server is needed to remove the job from the machine. During the loading, respectively the unloading, operation, both the machine and the loading, respectively the unloading, server are occupied. The objective function involves the minimization of the makespan. A Mixed Integer Linear Programming (MILP) model is proposed for the solution of this difficult problem. Due to the NP-hardness of the problem, a Variable Neighborhood Search (VNS) algorithm is proposed. The proposed VNS algorithm is compared against a state-of-the-art solver using a randomly generated data set. The results indicate that, the obtained solutions computed in a short amount of CPU time are of high quality. Specifically, the VNS solution approach outperformed IBM CPLEX Optimizer for instances with 15 and 20 jobs.
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
Abdekhodaee, A.H., Wirth, A.: Scheduling parallel machines with a single server: some solvable cases and heuristics. Comput. Oper. Res. 29(3), 295–315 (2002)
Bektur, G., Saraç, T.: A mathematical model and heuristic algorithms for an unrelated parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and a common server. Comput. Oper. Res. 103, 46–63 (2019)
Benmansour, R., Sifaleras, A., Mladenović, N. (eds.): Variable neighborhood search. LNCS, vol. 12010. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44932-2
Brucker, P., Dhaenens-Flipo, C., Knust, S., Kravchenko, S.A., Werner, F.: Complexity results for parallel machine problems with a single server. J. Sched. 5(6), 429–457 (2002)
Duarte, A., Mladenović, N., Sánchez-Oro, J., Todosijević, R.: Variable neighborhood descent. In: Martí, R., Panos, P., Resende, M. (eds.) Handbook of Heuristics, pp. 1–27. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-07153-4_9-1
Elidrissi, A., Benbrahim, M., Benmansour, R., Duvivier, D.: Variable neighborhood search for identical parallel machine scheduling problem with a single server. In: Benmansour, R., Sifaleras, A., Mladenović, N. (eds.) ICVNS 2019. LNCS, vol. 12010, pp. 112–125. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44932-2_8
Elidrissi, A., Benmansour, R., Benbrahim, M., Duvivier, D.: MIP formulations for identical parallel machine scheduling problem with single server. In: 2018 4th International Conference on Optimization and Applications (ICOA), pp. 1–6. IEEE (2018)
Glover, F.W., Kochenberger, G.A.: Handbook of Metaheuristics, vol. 57. Springer, Heidelberg (2006)
Hansen, P., Mladenović, N., Pérez, J.A.M.: Variable neighbourhood search: methods and applications. Ann. Oper. Res. 175(1), 367–407 (2010). https://doi.org/10.1007/s10479-009-0657-6
Hasani, K., Kravchenko, S.A., Werner, F.: Block models for scheduling jobs on two parallel machines with a single server. Comput. Oper. Res. 41, 94–97 (2014)
Jiang, Y., Zhang, Q., Hu, J., Dong, J., Ji, M.: Single-server parallel-machine scheduling with loading and unloading times. J. Comb. Optim. 30(2), 201–213 (2014). https://doi.org/10.1007/s10878-014-9727-z
Kim, M.Y., Lee, Y.H.: MIP models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single server. Comput. Oper. Res. 39(11), 2457–2468 (2012)
Liu, G.S., Li, J.J., Yang, H.D., Huang, G.Q.: Approximate and branch-and-bound algorithms for the parallel machine scheduling problem with a single server. J. Oper. Res. Soc. 70(9), 1554–1570 (2019)
Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)
Ou, J., Qi, X., Lee, C.Y.: Parallel machine scheduling with multiple unloading servers. J. Sched. 13(3), 213–226 (2010). https://doi.org/10.1007/s10951-009-0104-1
Sifaleras, A., Salhi, S., Brimberg, J. (eds.): Variable Neighborhood Search. LNCS, vol. 11328. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-15843-9
Torjai, L., Kruzslicz, F.: Mixed integer programming formulations for the biomass truck scheduling problem. CEJOR 24(3), 731–745 (2016). https://doi.org/10.1007/s10100-015-0395-6
Werner, F., Kravchenko, S.A.: Scheduling with multiple servers. Autom. Remote Control 71(10), 2109–2121 (2010). https://doi.org/10.1134/S0005117910100103
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Benmansour, R., Sifaleras, A. (2021). Scheduling in Parallel Machines with Two Servers: The Restrictive Case. In: Mladenovic, N., Sleptchenko, A., Sifaleras, A., Omar, M. (eds) Variable Neighborhood Search. ICVNS 2021. Lecture Notes in Computer Science(), vol 12559. Springer, Cham. https://doi.org/10.1007/978-3-030-69625-2_6
Download citation
DOI: https://doi.org/10.1007/978-3-030-69625-2_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-69624-5
Online ISBN: 978-3-030-69625-2
eBook Packages: Computer ScienceComputer Science (R0)