zbMATH — the first resource for mathematics

Parallel machine scheduling with tool loading. (English) Zbl 1465.90030
Summary: This paper presents a mixed integer programming approach that integrates the tool assignment and scheduling problems arising in parallel machine environments. There are a number of operations to be processed on parallel machines. Each operation requires a set of tools; however, the number of available tools are limited. Our objective is to minimize the makespan, i.e. the completion time of the final operation. We propose two different mathematical programming models for this problem. Since the problem is strongly NP-hard in general, finding the optimal solution requires extremely long computational times as the problem size increases. We therefore develop a tabu search algorithm in order to find near-optimal solutions within reasonable times.

90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
Tabu search
Full Text: DOI
[1] Pinedo, M., Scheduling: Theory, Algorithms and Systems (2008), Prentice-Hall: Prentice-Hall New Jersey
[2] Cheng, T. C.E.; Sin, C. C.S., A state-of-the-art review of parallel-machine scheduling research, Eur. J. Oper. Res., 47, 3, 271-292 (1990) · Zbl 0707.90053
[3] Mokotoff, E., Parallel machine scheduling problems: a survey, Asia-Pac. J. Oper. Res., 18, 2, 193-242 (2001) · Zbl 1042.90564
[4] Crama, Y., Combinatorial optimization models for production scheduling in automated manufacturing systems, Eur. J. Oper. Res., 99, 136-153 (1997) · Zbl 0923.90066
[5] Blazewicz, J.; Finke, G., Scheduling with resource management in manufacturing systems, Eur. J. Oper. Res., 76, 1-14 (1994) · Zbl 0925.90210
[6] Yeh, W.; Chuang, M.; Lee, W., Uniform parallel machine scheduling with resource consumption constraint, Appl. Math. Model., 39, 8, 2131-2138 (2015) · Zbl 1443.90199
[7] Cheng, B.; Yang, S.; Hu, X.; Chen, B., Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes, Appl. Math. Model., 36, 3161-3167 (2012) · Zbl 1252.90022
[8] Lin, Y., Fast LP models and algorithms for identical jobs on uniform parallel machines, Appl. Math. Model., 37, 3436-3448 (2013) · Zbl 1351.90099
[9] Edis, E.; Oguz, C.; Ozkarahan, I., Parallel machine scheduling with additional resources: Notation, classification, models and solution methods, Eur. J. Oper. Res., 230, 449-463 (2013) · Zbl 1317.90116
[10] Agnetis, A.; Alfieri, A.; Brandimarte, P.; Prinsecchi, P., Joint job/tool scheduling in a flexible manufacturing cell with no on-board tool magazine, Comput. Integr. Manuf. Syst., 10, 61-68 (1997)
[11] Kellerer, H.; Strusevich, V. A., Scheduling problems for parallel dedicated machines under multiple resource constraints, Disc. Appl. Math., 133, 45-68 (2004) · Zbl 1053.90039
[12] Avci, S.; Akturk, M., Tool magazine arrangement and operations sequencing on CNC machines, Comput. Oper. Res., 23, 1069-1081 (1996) · Zbl 0867.90061
[13] Kumar, N. S.; Sridharan, R., Simulation modeling and analysis of tool sharing and part scheduling decisions in single-stage multimachine flexible manufacturing systems, Robot. Comput. Integr. Manuf., 23, 361-370 (2007)
[14] Gamila, M. A.; Motavalli, S., A modeling technique for loading and scheduling problems in FMS, Robotic. Comput. Integr. Manuf., 19, 45-54 (2003)
[15] Roh, H.-K.; Kim, Y.-D., Due-date based loading and scheduling methods for a flexible manufacturing system with an automatic tool transporter, Int. J. Prod. Res., 35, 2989-3003 (1997) · Zbl 0942.90542
[16] Ventura, J. A.; Kim, D., Parallel machine scheduling with earliness-tardiness penalties and additional resource constraints, Comput. Oper. Res., 30, 1945-1958 (2003) · Zbl 1047.90023
[17] Turkcan, A.; Akturk, S.; Storer, R. H., Due date and cost-based FMS loading, scheduling and tool management, Int. J. Prod. Res., 45, 1183-1213 (2007) · Zbl 1128.90503
[18] Aldrin Raj, J.; Ravindran, D.; Saravanan, M.; Prabaharan, T. H., Simultaneous scheduling of machines and tools in multimachine flexible manufacturing systems using artificial immune system algorithm, Int. J. Comput. Int. Manuf., 27, 5, 401-414 (2014)
[19] Novas, J. M.; Henning, G. P., Integrated scheduling of resource-constrained flexible manufacturing systems using constraint programming, Expert Syst. Appl., 41, 2286-2299 (2014)
[20] Zeballos, L. J., A constraint programming approach to tool allocation and production scheduling in flexible manufacturing systems, Robotic. Comput. Integr. Manuf., 26, 725-743 (2010)
[21] Zeballos, L. J.; Quiroga, O. D.; Henning, G. P., A constraint programming model for the scheduling of flexible manufacturing systems with machine and tool limitations, Eng. Appl. Artif. Intell., 23, 229-248 (2010)
[22] Garey, M.; Johnson, D., Computer and Intractability. A Guide to the Theory of NP-Completeness (1979), Bell Laboratories
[23] Jans, R., Solving lot sizing problems on parallel identical machines using symmetry-breaking constraints, INFORMS J. Comput., 21, 123-136 (2009) · Zbl 1243.90147
[24] Degraeve, Z.; Gochet, W.; Jans, R., Alternative formulations for a layout problem in the fashion industry, Eur. J. Oper. Res., 143, 80-93 (2002) · Zbl 1073.90525
[25] Sherali, H.; Smith, J., Improving discrete model representations via symmetry considerations, Manag. Sci., 47, 1396-1407 (2001) · Zbl 1232.90309
[26] Sherali, H.; Fraticelli, B. M.P.; Meller, R., Enhanced model formulation for optimal facility layout, Oper. Res., 51, 629-644 (2003) · Zbl 1165.90545
[27] Margot, F., Exploiting orbits in symmetric ILP, Math. Program. Ser. B, 98, 3-21 (2002) · Zbl 1082.90070
[28] Margot, F., Pruning by isomorphism in branch-and-cut, Math. Program. Ser. B, 94, 71-90 (2002) · Zbl 1023.90088
[29] Glover, F., Future paths for integer programming and linkage to artificial intelligence, Comput. Oper. Res., 13, 533-549 (1986) · Zbl 0615.90083
[30] Glover, F.; Laguna, M., Tabu Search (1997), Kluwer Academic Publishers · Zbl 0930.90083
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.