×

zbMATH — the first resource for mathematics

Flow shop scheduling problem with position-dependent processing times. (English) Zbl 1458.90354
Summary: This study addresses a flow shop sequencing problem with position-dependent processing times. The aim of this work is to minimize the maximum tardiness and analyze the effects of the deterioration factor. This work is different from existing works in the literature, in that processing times are not per se deteriorating; instead, the resources deteriorate. This model allows the analysis of worker fatigue in a hand-intensive manufacturing system, such as in the luxury or textile industries. A case study of the problem is presented. In addition, a mathematical model, one sequencing heuristic, two improvement heuristics, and two metaheuristics are proposed, i.e., iterated local search and a greedy randomized adaptive search procedure. Computational experiments are carried out using random-generated instances. Results show the efficiency and efficacy of the proposed metaheuristics, and provide insights into the impact of the deterioration factor in flow shop scheduling problems.
MSC:
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
Software:
GRASP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alfares, H. K., Survey, Categorization, and comparison of recent tour scheduling literature, Ann. Oper. Res., 127, 1-4, 145-175, (2004) · Zbl 1087.90023
[2] Arroyo, J. E.C.; De Souza Pereira, A. A., A GRASP heuristic for the multi-objective permutation flowshop scheduling problem, Int. J. Adv. Manuf. Technol., 55, 5-8, 741-753, (2011)
[3] Baines, T. S.; Kay, J. M., Human performance modelling as an aid in the process of manufacturing system design: a pilot study, Int. J. Prod. Research, 40, 10, 2321-2334, (2002) · Zbl 1046.90524
[4] Baykasoglu, A.; Tasan, S. O.; Tasan, A. S.; Akyol, S. D., Modeling and solving assembly line design problems by considering human factors with a real‐life application, Human Factors Manage., 27, 2, 96-115, (2017)
[5] Bentefouet, F.; Nembhard, D. A., Optimal flow-line conditions with worker variability, Int. J. Prod. Econ., 141, 2, 675-684, (2013)
[6] Boudreau, J. W.; Hopp, W.; McClain, J. O.; Thomas, L. J., On the interface between operations and human resources management, Manuf. Service Oper. Manage., 5, 3, 179-202, (2003)
[7] Brucker, P., Scheduling Algorithms, (2007), Springer: Springer New York · Zbl 1126.90001
[8] Cheng, M.; Tadikamalla, P.; Shang, J.; Zhang, S., Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs, Eur. J. Oper. Res., 234, 3, 650-657, (2014) · Zbl 1304.90091
[9] Cheng, T. C.; Ding, Q.; Lin, B. M., A concise survey of scheduling with time-dependent processing times, Eur. J. Oper. Res, 152, 1, 1-13, (2004) · Zbl 1030.90023
[10] Dong, X.; Chen, P.; Huang, H., An improved iterated local search algorithm for the permutation flowshop problem with total flowtime, (Lee, G., Advances in Automation and Robotics, 1, LNEE, 122, (2011), Springer: Springer Berlin, Heidelberg), 41-48
[11] Festa, P.; Resende, M. G.C., An annotated bibliography of GRASP - Part II: applications, Int. Trans. Oper. Res., 16, 2, 131-172, (2009) · Zbl 1168.90582
[12] Gawiejnowicz, S., Time-Dependent Scheduling, (2008), Springer Publishing Company · Zbl 1155.90004
[13] Heizer, J.; Render, B., Dirección de la producción y de operaciones. Decisiones estratégicas. Dirección de la producción y de operaciones, Decisiones Estratégicas, (2007), Prentice Hall
[14] Huang, X.; Wang, J.-J., Machine scheduling problems with a position-dependent deterioration, Appl Math Model, 39, 10-11, 2897-2908, (2015)
[15] Juan, A.; Lourenço, H. L.; Mateo, M.; Luo, R.; Castella, Q., Using iterated local search for solving the flow-shop problem, Int. Trans. Oper. Res., 21, 1, 103-126, (2014) · Zbl 1291.90095
[16] Lee, W.-C.; Wu, C.-C.; Chung, Y.-H.; Liu, H.-C., Minimizing the total completion time in permutation flow shop with machine-dependent job deterioration rates, Comput. Oper. Res., 36, 6, 2111-2121, (2009) · Zbl 1179.90142
[17] Liu, M.; Chu, F.; He, J.; Yang, D.; Chu, C., Coke production scheduling problem: a parallel machine scheduling with batch preprocessings and location-dependent processing times, Comput. Oper. Res., 104, 37-48, (2019) · Zbl 1458.90322
[18] Liu, G.; Song, S.; Wu, C., Some heuristics for no-wait flowshops with total tardiness criterion, Comput. Oper. Res., 40, 2, 521-525, (2013) · Zbl 1349.90376
[19] 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)
[20] Maroto, C.; Ruiz, R., A comprehensive review and evaluation of permutation flowshop heuristics, Comput. Oper. Res., 40, 1, 117-128, (2004)
[21] Moreno-Camacho, C. A., Programación del personal de producción con productividades dinámicas, Tesis De Maestría En Gerencia de Operaciones, (2016), Universidad de La Sabana, Available online at:
[22] Moreno-Camacho, C. A.; Montoya-Torres, J. R., Workforce scheduling with social responsibility considerations, (Proceedings of the 2015 4th International Conference on Advanced Logistics and Transport (ICALT 2015). Proceedings of the 2015 4th International Conference on Advanced Logistics and Transport (ICALT 2015), Valenciennes, France, (2015)), 24-29
[23] Moreno-Camacho, C. A.; Montoya-Torres, J. R., Sustainability in production systems: a review of optimization methods studying social responsibility issues in workforce scheduling, (Borangiu, T.; Trentesaux, D.; Thomas, A.; McFarlane, D., Service Orientation in Holonic and Multi-Agent Manufacturing. Studies in Computational Intelligence, 640, (2016), Springer: Springer Cham)
[24] 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)
[25] Mosheiov, G., A note on scheduling deteriorating jobs, Math. Comput. Model., 41, 8-9, 883-886, (2005) · Zbl 1082.90038
[26] Moslehi, G.; Jafari, A., Minimizing the number of tardy jobs under piecewise-linear deterioration, Comput. Ind. Eng., 59, 4, 573-584, (2010)
[27] Neumann, W. P.; Dul, J., Human factors: spanning the gap between OM and HRM, Int. J. Oper. Prod. Manage., 30, 9, 923-950, (2010)
[28] Pan, Q. K.; Ruiz, R., A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime, Comput. Oper. Res., 40, 1, 117-128, (2013) · Zbl 1349.90386
[29] Pinedo, M. L., Scheduling. Scheduling: Theory, Algorithms, and Systems, (2012), Springer · Zbl 1239.90002
[30] Potts, C.; Van Wassenhove, L. N., A decomposition algorithm for the single machine total tardiness problem, Oper. Res. Lett., 1, 5, 177-181, (1982) · Zbl 0508.90045
[31] Prahalad, C. K., The blinders of dominant logic, Long Range Plan., 37, 2, 171-179, (2004)
[32] Resende, M. G.C.; González, J. L., GRASP: procedimientos de búsqueda miopes aleatorizados y adaptativos, Revista Iberoamericana de Inteligencia Artificial, 7, 19, 61-76, (2003)
[33] Ribeiro, C. C.; Rosseti, I.; Souza, R. C., Effective probabilistic stopping rules for randomized metaheuristics: GRASP implementations, (Coello, C. A.C., Learning and Intelligent Optimization. LION 2011. Lecture Notes in Computer Science, LNCS, 6683, (2011), Springer: Springer Berlin, Heidelberg), 146-160
[34] Ruiz-Torres, A. J.; Paletta, G.; Pérez, E., Parallel machine scheduling to minimize the makespan with sequence dependent deteriorating effects, Comput. Oper. Res., 40, 8, 2051-2061, (2013) · Zbl 1348.90307
[35] Rudek, R., Scheduling on parallel processors with varying processing times, Comput. Oper. Res., 81, 90-101, (2017) · Zbl 1391.90309
[36] Salazar, E.; Figueroa, B., Minimización de la tardanza para el flowshop flexible con setup utilizando heurísticas constructivas y un algoritmo genético, Ingeniare Revista chilena de ingeniería, 20, 89-98, (2012)
[37] Sánchez Herrera, S.; Montoya-Torres, J. R., Programación de la producción en flow-shops con productividad variable en industrias con mano de obra intensiva, (Maestría en Gerencia de Operaciones, Escuela Internacional de Ciencias Económicas y Administrativas. Maestría en Gerencia de Operaciones, Escuela Internacional de Ciencias Económicas y Administrativas, Chía, Colombia, (2016), Universidad de La Sabana)
[38] Senyigit, E.; Atici, U., Scheduling with job dependent learning effect and ergonomic risk deterioration, (Proceedings of the 2018 2nd International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT),. Proceedings of the 2018 2nd International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT),, Ankara, Turkey, (2018)), 1-4
[39] Taillard, E., Benchmarks for basic scheduling problems, Eur. J. Oper. Res., 64, 2, 278-285, (1993) · Zbl 0769.90052
[40] Thörnblad, K.; Patriksson, M., A note on the complexity of flow-shop scheduling with deteriorating jobs, Discrete Appl. Math., 159, 4, 251-253, (2011) · Zbl 1208.90079
[41] Vallada, E.; Ruiz, R.; Minella, G., Minimising total tardiness in the m-machine flowshop problem: a review and evaluation of heuristics and metaheuristics, Comput. Oper. Res., 35, 4, 1350-1373, (2008) · Zbl 1179.90160
[42] Wei, W., Single machine scheduling with stochastically dependent times, J. Schedul., 1-13, (2019), Forthcoming. DOI:
[43] Wang, J.-B, Flow shop scheduling jobs with position-dependent processing times, J. Appl. Math. Comput., 18, 1-2, 383-391, (2005) · Zbl 1077.90032
[44] Wang, X.-R.; Huang, X.; Wang, J.-B., Single-machine scheduling with linear decreasing deterioration to minimize earliness penalties, Appl. Math. Model., 35, 7, 3509-3515, (2011) · Zbl 1221.90051
[45] Wang, J.-B.; Liu, L. L., Two-machine flow shop problem with effects of deterioration and learning, Comput. Ind. Eng., 57, 3, 1114-1121, (2009)
[46] Wang, L.; Sun, L.-Y.; Sun, L.-H.; Wang, J.-B., On three-machine flow shop scheduling with deteriorating jobs, Int. J. Prod. Econ., 125, 1, 185-189, (2010)
[47] Wang, J.-B.; Wang, M. Z., Minimizing makespan in three-machine flow shops with deteriorating jobs, Comput. Oper. Res., 40, 2, 547-557, (2013) · Zbl 1349.90410
[48] Wang, X.-Y.; Wang, M.-Z.; Wang, J.-B., Flow shop scheduling to minimize makespan with decreasing time-dependent job processing times, Comput. Ind. Eng., 60, 4, 840-844, (2011)
[49] Yang, S.-J., Parallel machines scheduling with simultaneous considerations of position-dependent deterioration effects and maintenance activities, J. Chin. Inst. Ind. Eng., 28, 4, 270-280, (2011)
[50] Yang, D.-L.; Cheng, T. C.E.; Yang, S.-J.; Shu, C.-J., Unrelated parallel-machine scheduling with aging effects and multi-maintenance activities, Comput. Oper. Res., 39, 7, 1458-1464, (2012) · Zbl 1251.90202
[51] Yin, Y.; Wu, W.-H.; Cheng, T. C.; Wu, C.-C., Single-Machine scheduling with time-dependent and position-dependent deteriorating jobs, Int. J. Comput. Integr.Manuf., 28, 7, 781-790, (2015)
[52] Zhao, C.; Tang, H., A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints, Optim. Lett., 5, 1, 183-190, (2011) · Zbl 1213.90127
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.