Abstract
Traditional deterministic scheduling problems consider that processing times of jobs are fixed and constant over time. However, this assumption is not realistic in practice in hand-intensive manufacturing contexts. To deal with this, the current paper studies the deterioration effect of processing times on a parallel machine scheduling problem. In such a case, job processing times depend on the position of jobs in the execution sequence. The objective function is the minimization of the maximum delay of the set of jobs, that is the makespan. A mixed-integer linear programming model is provided for the basic case in which the processing time of jobs deteriorate only as a function of their position in the schedule. Then, two original extensions are proposed. The first one considers that both the position and the worker do impact the processing time, while in the second situation workers can have a break after a given period of time. Preliminary experiments are carried out to illustrate the impact of such situations on the objective function. Results are promising.
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
Alfares, H.K.: Survey, categorization, and comparison of recent tour scheduling literature. Ann. Oper. Res. 127(1–4), 145–175 (2004)
Boudreau, J.W., Hopp, W., Mcclain, J.O., Thomas, L.J.: On the interface between operations and human resources management. Manuf. Serv. Oper. Manag. 5(3), 179–202 (2003)
Chen, W., Guo, P., Zhang, Z., Zeng, M., Liang, J.: Variable neighborhood search for parallel machines scheduling problem with step deteriorating jobs. Math. Probl. Eng. 2012 (2012). Article no. 928312
Gerstl, E., Mosheiov, G.: Scheduling on parallel identical machines with job-rejection and position-dependent processing times. Inf. Process. Lett. 112(19), 743–747 (2012)
Huang, X., Wang, M.-Z.: Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties. Appl. Math. Model. 35(3), 1349–1353 (2011)
Ji, M., Cheng, T.C.: Parallel-machine scheduling of simple linear deteriorating jobs. Theoret. Comput. Sci. 410(38–40), 3761–3768 (2009)
Lawer, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: algorithms and complexity. Centre for Mathematics and Computer Science Report BS-R8909, Stichting Mathematisch Centrum, Amsterdam, Holland (1989)
Lodree, E.J., Geiger, C.D., Jiang, X.: Taxonomy for integrating scheduling theory and human factors: review and research opportunities. Int. J. Ind. Ergon. 39(1), 39–51 (2009)
Miao, C., Zou, J.: Parallel-machine scheduling with time-dependent and machine availability constraints. Math. Probl. Eng. 2015 (2015). Article no. 956158
Montoya-Torres, J.R., Sánchez, S., Moreno-Camacho, C.: A literature-based assessment of human factors in shop scheduling problems. IFAC-PapersOnLine 52(10), 49–54 (2019)
Moreno-Camacho, C.A., Montoya-Torres, J.R.: Workforce scheduling with social responsibility considerations. In: Proceedings of the 4th IEEE International Conference on Advanced Logistics and Transport (ICALT), pp. 24–29. IEEE Publishing (2015)
Moreno-Camacho, C.A., Montoya-Torres, J.R., Vélez-Gallego, M.C.: A comparison of mixed-integer linear programming models for workforce scheduling with position-dependent processing times. Eng. Optim. 50(6), 917–932 (2018)
Mosheiov, G.: A note on scheduling deteriorating jobs. Math. Comput. Model. 41(8–9), 883–886 (2005)
Mosheiov, G.: Minimizing total absolute deviation of job completion times: extensions to position-dependent processing times and parallel identical machines. J. Oper. Res. Soc. 59, 1422–1424 (2008)
Mosheiov, G.: A note: multi-machine scheduling with general position-based deterioration to minimize total load. Int. J. Prod. Econ. 135(1), 523–525 (2012)
Petrovic, S., Vanden Berghe, G.: A comparison of two approaches to nurse rostering problems. Ann. Oper. Res. 194(1), 365–384 (2012)
Puente, J., Gómez, A., Fernández, I., Priore, P.: Medical doctor rostering problem in a hospital emergency department by means of genetic algorithms. Comput. Ind. Eng. 56(4), 1232–1242 (2009)
Thompson, G.M., Goodale, J.C.: Variable employee productivity in workforce scheduling. Eur. J. Oper. Res. 170(2), 376–390 (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 IFIP International Federation for Information Processing
About this paper
Cite this paper
Montoya-Torres, J.R., Botta-Genoulaz, V., Materzok, N., Gíslason, Þ.P., Mendiela, S. (2021). Modeling the Parallel Machine Scheduling Problem with Worker- and Position-Dependent Processing Times. In: Dolgui, A., Bernard, A., Lemoine, D., von Cieminski, G., Romero, D. (eds) Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems. APMS 2021. IFIP Advances in Information and Communication Technology, vol 632. Springer, Cham. https://doi.org/10.1007/978-3-030-85906-0_39
Download citation
DOI: https://doi.org/10.1007/978-3-030-85906-0_39
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-85905-3
Online ISBN: 978-3-030-85906-0
eBook Packages: Computer ScienceComputer Science (R0)
