Flow shop scheduling with heterogeneous workers. (English) Zbl 1304.90086
Summary: We propose an extension to the flow shop scheduling problem named Heterogeneous Flow Shop Scheduling Problem (Het-FSSP), where two simultaneous issues have to be resolved: finding the best worker assignment to the workstations, and solving the corresponding scheduling problem. This problem is motivated by Sheltered Work centers for disabled, whose main objective is the labor integration of persons with disabilities, an important aim not only for these centers but for any company desiring to overcome the traditional standardized vision of the workforce. In such a scenario the goal is to maintain high productivity levels by minimizing the maximum completion time, while respecting the diverse capabilities and paces of the heterogeneous workers, which increases the complexity of finding an optimal schedule. We present a mathematical model that extends a flow shop model to admit a heterogeneous worker assignment, and propose a heuristic based on scatter search and path relinking to solve the problem. Computational results show that this approach finds good solutions within a short time, providing the production managers with practical approaches for this combined assignment and scheduling problem.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C10 | Integer programming |
Software:
Scatter SearchReferences:
| [1] | Blum, C.; Miralles, C., On solving the assembly line worker assignment and balancing problem via beam search, Computers & Operations Research, 38, 328-339 (2011) · Zbl 1231.90256 |
| [2] | Brucker, P.; Heitmann, S.; Hurink, J., Flow-shop problems with intermediate buffers, OR Spectrum, 25, 549-574 (2003) · Zbl 1042.90016 |
| [3] | Carlier, J., Ordonnancements a contraintes disjonctives. R.A.I.R.O, Recherche operationelle/Operations Research, 12, 333-351 (1978) · Zbl 0401.90052 |
| [4] | Carlier, J.; Pinson, E., A practical use of Jackson’s preemptive schedule for solving the job-shop problem, Annals of Operations Research, 26, 269-287 (1990) · Zbl 0709.90061 |
| [5] | Chen, B.; Glass, C. A.; Potts, C. N.; Strusevich, V. A., A new heuristic for three-machine flow shop scheduling, Operation Research, 44, 891-898 (1996) · Zbl 0879.90112 |
| [6] | Companys, R.; Mateo, M., Different behaviour of a double branch-and-bound algorithm on \(fm | prmu | c_{\max}\) and \(fm | block | c_{\max}\) problems, Computers & Operations Research, 34, 938-953 (2007) · Zbl 1107.90016 |
| [7] | Corominas, A.; Ferrer, L.; Pastor, R., Assembly line balancing: General resource-constrained case, International Journal of Production Research, 49, 3527-3542 (2012) |
| [8] | Corominas, A.; Pastor, R.; Plans, J., Balancing assembly line with skilled and unskilled workers, Omega, 36, 1126-1132 (2008) |
| [9] | Erel, E.; Sabuncuoglu, I.; Sekerci, H., Stochastic assembly line balancing using beam search, International Journal of Production Research, 43, 1411-1426 (2005) · Zbl 1068.90045 |
| [10] | Gonzalez, T.; Sahni, S., Flowshop and jobshop schedules: Complexity and approximation, Operation Research, 26, 36-52 (1978) · Zbl 0371.90061 |
| [11] | Kalczynski, P. J.; Kamburowski, J., On recent modifications and extensions of the NEH heuristic for flow shop sequencinga, Foundation of Computer Science and Decision Sciences, 36, 17-33 (2011) · Zbl 1211.90087 |
| [12] | Koulamas, C., A new constructive heuristic for the flowshop scheduling problem, European Journal of Operational Research, 105, 66-71 (1998) · Zbl 0957.90053 |
| [13] | Ladhari, T.; Haouari, M., A computational study of the permutation flow shop problem based on a tight lower bound, Computers & Operations Research, 32, 1831-1847 (2005) · Zbl 1074.90018 |
| [14] | Laguna, M.; Martí, R., Scatter search: Methodology and implementations in C (2003), Kluwer Academic Publishers · Zbl 1055.68103 |
| [15] | Leisten, R., Flowshop sequencing problems with limited buffer constraints, International Journal of Production Research, 28, 2085-2100 (1990) · Zbl 0707.90054 |
| [16] | Liao, C. J.; Liao, L. M.; Tseng, C. T., A performance evaluation of permutation vs. non-permutation schedules in a flowshop, International Journal of Production Research, 44, 4297-4309 (2006) |
| [17] | Lin, S.-W.; Ying, K.-C., Applying a hybrid simulated annealing and tabu search approach to non-permutation flowshop scheduling problems, International Journal of Production Research, 47, 1411-1424 (2009) |
| [18] | Miralles, C.; Garcia-Sabater, J. P.; Andrés, C.; Cardos, M., Advantages of assembly lines in Sheltered Work Centres for Disabled. A case study, International Journal of Production Research, 110, 187-197 (2007) |
| [19] | Miralles, C.; Marin-Garcia, J.; Ferrus, G.; Costa, A., OR/MS tools for integrating people with disabilities into employment. A study on Valencia’s sheltered work centres for disabled, International Transactions in Operations Research, 17, 457-473 (2010) |
| [20] | Moreira, M. C.O.; Ritt, M.; Costa, A. M.; Chaves, A. A., Simple heuristics for the assembly line worker assignment and balancing problem, Journal of Heuristics, 18, 505-524 (2012) |
| [21] | Nagarajan, V.; Sviridenko, M., Tight bounds for permutation flow shop scheduling, Mathematics of Operations Research, 34, 417-427 (2009) · Zbl 1231.90209 |
| [22] | Nawaz, M.; Enscore, E.; Ham, I., A heuristic algorithm for the \(m\)-machine, \(n\)-job flow-shop sequencing problem, Omega, 11, 91-95 (1983) |
| [23] | Nowicki, E.; Smutnicki, C., A fast taboo search algorithm for the job shop problem, Management Sciences, 42, 797-813 (1996) · Zbl 0880.90079 |
| [24] | Potts, C. N.; Strusevich, V. A., Fifty years of scheduling: A survey of milestones, Journal of the Operational Research Society, 60, S41-S68 (2009) · Zbl 1168.90311 |
| [25] | Pugazhendhi, S.; Thiagarajan, S.; Rajendran, C.; Anantharaman, N., Performance enhancement by using non-permutation schedules in flowline-based manufacturing systems, Computers & Industrial Engineering, 44, 133-157 (2002) |
| [26] | Rajendran, C.; Ziegler, H., Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, European Journal of Operation Research, 155, 426-438 (2004) · Zbl 1045.90032 |
| [27] | Resende, M. G.; Ribeiro, C. C.; Glover, F.; Martí, R., Scatter search and path-relinking: Fundamentals, advances, and applications, (Gendreau, M.; Potvin, J.-Y., Handbook of metaheuristics (2010), Springer), 87-107 |
| [28] | Rossi, A.; Lanzetta, M., Scheduling flow lines with buffers by ant colony digraph, Expert System with Applications, 40, 3328-3340 (2013) |
| [29] | Ruiz, R.; Marato, C.; Alcaraz, J., Two new robust genetic algorithms for the flowshop scheduling problem, Omega, 34, 461-476 (2006) |
| [30] | Ruiz, R.; Maroto, C., A comprehensive review and evaluation of permutation flowshop heuristics, European Journal of Operation Research, 165, 479-494 (2005) · Zbl 1066.90038 |
| [31] | Ruiz, R.; Stützle, T., A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operation Research, 177, 2033-2049 (2007) · Zbl 1110.90042 |
| [32] | Sadjadi, S. J.; Bouquard, J. L.; Ziaee, M., An ant colony algorithm for the flowshop scheduling problem, Journal of Applied Science, 8, 3938-3944 (2008) |
| [33] | Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operation Research, 64, 278-285 (1993) · Zbl 0769.90052 |
| [35] | Tandon, M.; Cummings, P.; Levan, M., Flowshop sequencing with non-permutation schedules, Computers & Chemical Engineering, 15, 601-607 (1991) |
| [36] | Tasgetiren, M.; Liang, Y.; Sevkli, M.; Gencyilmaz, G., A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem, European Journal of Operation Research, 177, 1930-1947 (2007) · Zbl 1110.90044 |
| [38] | Yagmahan, B.; Yenisey, M. M., A multi-objective ant colony system algorithm for flow shop scheduling problem, Expert System with Applications, 37, 1361-1368 (2010) |
| [39] | Ying, K.-C., Solving non-permutation flowshop scheduling problems by an effective iterated greedy heuristic, The International Journal of Advanced Manufacturing Technology, 38, 348-354 (2008) |
| [40] | Ying, K.-C.; Lin, S.-W., Multi-heuristic desirability ant colony system heuristic for non-permutation flowshop scheduling problems, The International Journal of Advanced Manufacturing Technology, 33, 739-802 (2007) |
| [41] | Zobolas, G. I.; Tarantilis, C. D.; Ioannou, G., Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm, Computers & Operations Research, 36, 1249-1267 (2009) · Zbl 1160.90490 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
