×

Minimizing the number of workers in a paced mixed-model assembly line. (English) Zbl 1403.90284

Summary: We study a problem of minimizing the maximum number of identical workers over all cycles of a paced assembly line comprised of \(m\) stations and executing \(n\) parts of \(k\) types. There are lower and upper bounds on the workforce requirements and the cycle time constraints. We show that this problem is equivalent to the same problem without the cycle time constraints and with fixed workforce requirements. We prove that the problem is NP-hard in the strong sense if \(m = 4\) and the workforce requirements are station independent, and present an integer linear programming model, an enumeration algorithm and a dynamic programming algorithm. Polynomial in \(k\) and polynomial in \(n\) algorithms for special cases with two part types or two stations are also given. Relations to the bottleneck traveling salesman problem and its generalizations are discussed.

MSC:

90B30 Production models
90C27 Combinatorial optimization
90C60 Abstract computational complexity for mathematical programming problems
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Akagi, F.; Osaki, H.; Kikuchi, S., A method for assembly line balancing with more than one worker in each station, International Journal of Production Research, 21, 5, 755-770, (1983)
[2] Arkin, E. M.; Chiang, Y.; Mitchell, J. S.B.; Skiena, S. S.; Yang, T., On the maximum scatter traveling salesman problem, SIAM Journal on Computing, 29, 2, 515-544, (1999) · Zbl 0942.90035
[3] Bar-Noy, A.; Dreizin, V.; Patt-Shamir, B., Efficient algorithms for periodic scheduling, Computer Networks, 45, 155-173, (2004) · Zbl 1072.68013
[4] Bartholdi, J. J.; Orlin, J. B.; Ratliff, H. D., Cyclic scheduling via integer programs with circular ones, Operations Research, 28, 5, 1074-1085, (1980) · Zbl 0451.90075
[5] Battaïa, O.; Delorme, X.; Dolgui, A.; Hagemann, J.; Horlemann, A.; Kovalev, S.; Malyutin, S., Workforce minimization for a mixed-model assembly line in the automotive industry, International Journal of Production Economics, 170(B), 489-500, (2015)
[6] Battaïa, O.; Dolgui, A., A taxonomy of line balancing problems and their solution approaches, International Journal of Production Economics, 142, 2, 259-277, (2013)
[7] Bobrova, E. A.; Servakh, V. V., Construction of cyclic schedules in presence of parallel machines, Journal of Applied and Industrial Mathematics, 11, 1, 17-25, (2017) · Zbl 1374.90151
[8] Brucker, P.; Kampmeyer, T., A general model for cyclic machine scheduling problems, Discrete Applied Mathematics, 156, 13, 2561-2572, (2008) · Zbl 1152.90430
[9] Burkard, R. E.; Deineko, V. G.; Van Dal, R.; Van der Veen, J. A.A.; Woeginger, G. A., Well-solvable special cases of the traveling salesman problem: a survey, SIAM Review, 40, 3, 496-546, (1998) · Zbl 1052.90597
[10] Burkard, R. E.; Sandholzer, W., Efficiently solvable special cases of bottleneck travelling salesman problems, Discrete Applied Mathematics, 32, 1, 61-76, (1991) · Zbl 0747.90081
[11] Che, A.; Kats, V.; Levner, E., An efficient bicriteria algorithm for stable robotic flow shop scheduling, European Journal of Operational Research, 260, 3, 964-971, (2017) · Zbl 1403.90311
[12] Chiang, Y. J., New approximation results for the maximum scatter TSP, Algorithmica, 41, 4, 309-341, (2005) · Zbl 1070.90136
[13] Chretienne, P., The basic cyclic scheduling problem with deadlines, Discrete Applied Mathematics, 30, 109-123, (1991) · Zbl 0729.90051
[14] Dalle Mura, M.; Dini, G., Worker skills and equipment optimization in assembly line balancing by a genetic approach, Procedia CIRP, 44, 102-107, (2016)
[15] Dauscha, W.; Modrow, H. D.; Neumann, A., On cyclic sequence types for constructing cyclic schedule, Zeitschrift fur Operations Research, 29, 1-30, (1985) · Zbl 0563.90057
[16] De Bruecker, P.; Van denBergh, J.; Beliïen, J.; Demeulemeester, E., Workforce planning incorporating skills: state of the art, European Journal of Operational Research, 243, 1, 1-16, (2015) · Zbl 1346.90470
[17] Dolgui, A.; Kovalev, S.; Kovalyov, M. Y.; Malyutin, S.; Soukhal, A., Optimal workforce assignment to operations of a paced assembly line, European Journal of Operational Research, 264, 200-211, (2018) · Zbl 1380.90150
[18] Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[19] Gilmore, P. C.; Gomory, R. E., Sequencing a one state-variable machine: A solvable case of the traveling salesman problem, Operations Research, 12, 655-679, (1964) · Zbl 0126.36006
[20] Gilmore, P. C.; Lawler, E. L.; Shmoys, D. B., Well-solved special cases, (Lawler, E. L.; Lenstra, J. K.; Kan, A. H.G. R.; Shmoys, D. B., The traveling salesman problem, (1985), Wiley Chichester), 87-143 · Zbl 0631.90081
[21] Hall, N. G.; Lee, T. E.; Posner, M. E., The complexity of cyclic shop scheduling problems, Journal of Scheduling, 5, 4, 307-327, (2002) · Zbl 1009.90048
[22] Hanen, C.; Munier, A., Cyclic scheduling on parallel processors: on overview, (Chretienne, P.; Coffman, E. G.; Lenstra, J. K.; Liu, Z., Scheduling theory and its applications, chapter 4, (1995), John Wiley and Sons New York), 194-226
[23] Hitz, K. L., Scheduling of flow shops II. report no. LIDS-r-879, Laboratory for information and decision systems, (1980), MIT, Cambridge Massachusetts
[24] Hochbaum, D. S.; Levin, A., Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms, Discrete Optimization, 3, 4, 327-340, (2006) · Zbl 1112.90023
[25] Kabadi, S. N.; Punnen, A. P., The bottleneck TSP, (Gutin, G.; Punnen, A. P., The traveling salesman problem and its variations. combinatorial optimization, vol 12, (2007), Springer Boston, MA) · Zbl 1113.90358
[26] Kimbrel, T.; Sviridenko, M., High-multiplicity cyclic job shop scheduling, Operations Research Letters, 36, 5, 574-578, (2008) · Zbl 1210.90089
[27] Kouvelis, P.; Karabati, S., Cyclic scheduling in synchronous production lines, IIE Transactions, 31, 8, 709-719, (1999)
[28] La Rusic, J.; Punnen, A. P., The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis, Computers and Operations Research, 43, 20-35, (2014) · Zbl 1348.90546
[29] Lee, C. Y.; Vairaktarakis, G. L., Workforce planning in mixed model assembly systems, Operations Research, 45, 4, 553-567, (1997) · Zbl 0887.90081
[30] Levner, E.; Kats, V.; Alcaide, D.; Cheng, T. C.E., Complexity of cyclic scheduling problems: a state-of-the-art survey, Computers and Industrial Engineering, 59, 352-361, (2010)
[31] Lutz, C. M.; Davis, K. R., Development of operator assignment schedules: A DSS approach, Omega, 22, 1, 57-67, (1994)
[32] Polat, O.; Kalayci, C. B.; Mutlu, O.; Gupta, S. M., A two-phase variable neighbourhood search algorithm for assembly line worker assignment and balancing problem type-II: an industrial case study, International Journal of Production Research, 54, 3, 722-741, (2016)
[33] Punnen, A. P., Traveling salesman problem under categorization, Operations Research Letters, 12, 89-95, (1992) · Zbl 0768.90077
[34] Ritt, M.; Costa, A. M.; Miralles, C., The assembly line worker assignment and balancing problem with stochastic worker availability, International Journal of Production Research, 54, 3, 907-922, (2016)
[35] Sawik, T., A mixed integer program for cyclic scheduling of flexible flow lines, Bulletin of the Polish Academy of Sciences Technical Sciences, 62, 1, 121-128, (2014)
[36] Timkovsky, V. G., Cycle shop scheduling, (Leung, J. Y.T., Handbook of scheduling: algorithms, models, and performance analysis, (2004), Chapman & Hall/CRC, Boca Raton London), 127-148
[37] Vairaktarakis, G. L., On gilmore-gomory’s open question for the bottleneck TSP, Operations Research Letters, 31, 6, 483-491, (2003) · Zbl 1052.90068
[38] Vairaktarakis, G. L., Simple algorithms for gilmore-gomory’s traveling salesman and related problems, Journal of Scheduling, 6, 499-520, (2003) · Zbl 1154.90498
[39] Vairaktarakis, G. L.; Cai, X.; Lee, C. Y., Workforce planning in synchronous production systems, European Journal of Operational Research, 136, 2002, 551-572, (2002) · Zbl 1008.90017
[40] Vairaktarakis, G. L.; Szmerekovsky, J. G.; Xu, J., Level workforce planning for multistage transfer lines, Naval Research Logistics, 63, 577-590, (2016)
[41] Vairaktarakis, G. L.; Winch, J. K., Worker cross-training in paced assembly lines, Manufacturing & Services Operations Management, 1, 2, 112-131, (1999)
[42] van der Veen, J. A.A., An O(n) algorithm to solve the bottleneck traveling salesman problem restricted to ordered product matrices, Discrete Applied Mathematics, 47, 57-75, (1993) · Zbl 0801.90120
[43] Wilson, J. M., Formulation of a problem involving assembly lines with multiple Manning of work stations, International Journal of Production Research, 24, 1, 59-63, (1986) · Zbl 0584.90040
[44] Winch, J. K.; Cai, X.; Vairaktarakis, G. L., Cyclic job scheduling in paced assembly lines with cross-trained workers, International Journal of Production Research, 45, 4, 803-828, (2007) · Zbl 1128.90504
[45] Woods, B., Punnen, A., & Stephen, T. (2015). Linear time algorithm for the 3-neighbour traveling salesman problem on Halin graphs and extensions. ArXiv: 1504.02151v3; Woods, B., Punnen, A., & Stephen, T. (2015). Linear time algorithm for the 3-neighbour traveling salesman problem on Halin graphs and extensions. ArXiv: 1504.02151v3
[46] Yilmaz, H.; Yilmaz, M., A multi-manned assembly line balancing problem with classified teams: a new approach, Assembly Automation, 36, 1, 51-59, (2016)
[47] Zacharia, P. T.; Nearchou, A. C., A population-based algorithm for the bi-objective assembly line worker assignment and balancing problem, Engineering Applications of Artificial Intelligence, 49(C), 1-9, (2016)
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.