Combinatorial optimization models for production scheduling in automated manufacturing systems

[en] Production planning and scheduling models arising in automated manufacturing environments exhibit several features not encountered in models developed for traditional production systems. For instance, models of automated facilities typically include tooling constraints which reflect the possibility for a machine to use different tools in order to perform successive operations, within limits imposed by the size of the tool magazine. Also, these models often account for the existence of flexible material handling systems whose activities must be synchronized with the machining operations in order to optimize system utilization. In this paper, we describe a few interesting combinatorial optimization problems proposed in this framework, we point to their relationships with models investigated in seemingly remote areas, and we identify a number of challenging open problems.

Disciplines :

Production, distribution & supply chain management
Quantitative methods in economics & management

Author, co-author :

Crama, Yves ; Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production

Language :

English

Title :

Combinatorial optimization models for production scheduling in automated manufacturing systems

Publication date :

1997

Journal title :

European Journal of Operational Research

ISSN :

0377-2217

eISSN :

1872-6860

Publisher :

Elsevier Science, Amsterdam, Netherlands

Volume :

Pages :

136-153

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 18 October 2016

Statistics

Number of views

130 (1 by ULiège)

Number of downloads

1423 (2 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Agnetis, A., Arbib, C. and Lucertini, M., "Combinatorial models for manufacturing: Optimizing flow management in flexible production systems", in: T.A. Ciriani and R.C. Leachman (eds.), Optimization in Industry, John Wiley and Sons, New York, 1993, 81-99.
Agnetis, A., Lucertini, M. and Nicoló, F., "Flow management in flexible manufacturing cells with pipeline operations", Management Science 39 (1993) 294-306.
Agnetis, A., Pacciarelli, D. and Rossi, F., "Lot scheduling in a two-machine cell with swapping devices", IIE Transactions 28 (1996) 911-917.
Ahmadi, R.H., "A hierarchical approach to design, planning, and control problems in electronic circuit card manufacturing, in: R.K. Sarin (ed.), Perspectives in Operations Management, Kluwer Academic Publishers, Dordrecht, 1993, 409-429.
Amoako-Gyampah, K., "A comparative study of FMS tool allocation and part type selection approaches for a varying part type mix", The International Journal of Flexible Manufacturing Systems 6 (1994) 179-207.
Armstrong, R., Lei, L. and Gu, S., "A bounding scheme for deriving the minimal cycle time of a single-transporter N-stage process with time-window constraints", European Journal of Operational Research 78 (1994) 130-140.
Asfahl, C.R., Robots and Manufacturing Automation, John Wiley and Sons, New York, 1985.
Askin, R.G. and Standridge, C.R., Modeling and Analysis and Manufacturing Systems, John Wiley and Sons, New York, 1993.
Balas, E. and Mazzola, J.B., "Nonlinear 0-1 programming: I. Linearization techniques", Mathematical Programming 30 (1984) 1-21.
Bard, J.F., "A heuristic for minimizing the number of tool switches on a flexible machine", IIE Transactions (1988) 382-391.
Belady, L.A., "A study of replacement algorithms for virtual storage computers", IBM Systems Journal 5 (1966) 78-101.
Berrada, M. and Stecke, K.E., "A branch and bound approach for machine load balancing in flexible manufacturing systems", Management Science 32 (1986) 1316-1335.
Blazewicz, J., Burkard, R., Finke, G. and Woeginger, G., "Vehicle scheduling in two-cycle flexible manufacturing systems", Math. and Computer Modelling 20 (1994) 19-31.
Blazewicz, J., Ecker, K.. Schmidt, G. and Weglarz, J., Scheduling in Computer and Manufacturing Systems, Springer-Verlag, Berlin, Heidelberg, 1993.
Blazewicz, J., Eiselt, H.A., Finke, G., Laporte, G. and Weglarz, J., "Scheduling tasks and vehicles in a flexible manufacturing system", The International Journal of Flexible Manufacturing Systems 4 (1991) 5-16.
Blazewicz, J. and Finke, G., "Scheduling with resource management in manufacturing systems", European Journal of Operational Research 76 (1994) 1-14.
Blazewicz, J., Finke, G.. Haupt, R. and Schmidt, G., "New trends in machine scheduling", European Journal of Operational Research 37 (1988) 303-317.
Browne. J., Dubois, D., Rathmill, K. and Sethi, S.P. and Stecke, K.E., "Classification of flexible manufacturing systems", The FMS Magazine 2 (1984) 114-117.
Buzacott, J.A. and Shantikumar, J.G., Stochastic Models of Manufacturing Systems, Prentice Hall, Englewood Cliffs, NJ, 1993.
Chaillou, P., Hansen, P. and Mahieu, Y., "Best network flow bounds for the quadratic knapsack problem", in: B. Simeone (ed.), Combinatorial Optimization, Springer-Verlag, Berlin, 1989, 225-235.
Cohen, G., Dubois, D., Quadrat, J.P. and Viot, M., "A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing", IEEE Transactions on Automatic Control AC-30 (1985) 210-220.
Crama, Y. and van de Klundert, J., "Approximation algorithms for integer covering problems via greedy column generation", RAIRO - Operations Research 28 (1994) 283-302.
Crama, Y. and van de Klundert, J., "Cyclic scheduling of identical parts in a robotic cell, working paper (1994). To appear in Operations Research;
Crama, Y. and van de Klundert, J., "The approximability of tool management problems", working paper (1996).
Crama, Y., Kolen, A.W.J., Oerlemans, A.G. and Spieksma, F.C.R., "Throughput rate optimization in the automated assembly of printed circuit boards", Annals of Operations Research 26 (1990) 455-480.
Crama, Y., Kolen, A.W.J., Oerlemans, A.G. and Spieksma, F.C.R., "Minimizing the number of tool switches on a flexible machine", The International Journal of Flexible Manufacturing Systems 6 (1994) 33-54.
Crama, Y. and Mazzola, J.B., "On tool loading, dense subhypergraphs and nonlinear knapsack problems", unpublished manuscript, 1992.
Crama, Y. and Mazzola, J.B., "Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and FMS part-selection problems", Annals of Operations Research 58 (1995) 99-128.
Crama, Y. and Oerlemans, A.G., "A column generation approach to job grouping for flexible manufacturing systems", European Journal of Operational Research 78 (1994) 58-80.
Crama, Y., Oerlemans, A.G. and Spieksma, F.C.R., Production Planning in Automated Manufacturing. 2nd Ed., Springer-Verlag, Berlin, 1996.
Crama, Y. and Oosten, M., "Models for machine-part grouping in cellular manufacturing", International Journal of Production Research 34 (1996) 1693-1713.
Dietrich, B.L., Lee, J. and Lee, Y.S., "Order selection on a single machine with high set-up costs", Annals of Operations Research 43 (1993) 379-396.
Finke, G., Gueguen, C. and Brauner, N., "Robotic cells with buffer space", in: R. O'Connor and P. Magee (eds.), ECCO IX - Conference Proceedings, Center for Teaching Computing, Dublin, Ireland, 1996.
Follonier, J.-P., "Minimization of the number of tool switches on a flexible manufacturing machine", JORBEL -Belgian J. of Operations Research, Statistics and Computer Science 34 (1994) 55-72.
Fulkerson, D.R. and Gross, D.A., "Incidence matrices and interval graphs", Pacific Journal of Mathematics 15 (1965) 835-855.
Gallo, G., Hammer, P.L. and Simeone, B., "Quadratic knapsack problems", Mathematical Programming Study 12 (1980) 132-149.
Gallo, G. and Simeone, B., "On the supermodular knapsack problem", Mathematical Programming 45 (1988) 295-309.
Gilmore, P.C., Lawler, E.L. and Shmoys, D.B., "Well solved special cases", in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys (eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley and Sons Ltd., Chichester, New York, Brisbane, Toronto, Singapore. 1985, 87-143.
Glover, F. and Woolsey, E., "Converting the 0-1 polynomial programming problem to a 0-1 linear program", Operations Research 22 (1974) 180-182.
Goldschmidt, O., Hochbaum, D.S. and Yu, G., "Component assembly in the semiconductor industry: A study of covering in graphs and hypergraphs", Technical Report ORP92-5, The University of Texas at Austin, 1992.
Goldschmidt, O., Nehme, D. and Yu, G., "On the set-union knapsack problem", Naval Research Logistics 41 (1994) 833-842.
Gray. A.E., Seidmann, A. and Stecke, K.E., "A synthesis of decision models for tool management in automated manufacturing", Management Science 39 (1993) 549-567.
Gunasekaran, A., Martikainen, T. and Yli-Olli, P., "Flexible manufacturing systems: An investigation for research and applications", European Journal of Operational Research 66 (1993) 1-26.
Gupta, Y.P. and Goyal, S., "Flexibility of manufacturing systems: Concepts and measurements", European Journal of Operational Research 43 (1989) 119-135.
Hall, N.G., Kamoun, H. and Sriskandarajah, C., "Scheduling in robotic cells: Classification, Two and three machine cells", Working Paper 93-56. College of Business, The Ohio State University, 1993. Operations Research, to appear.
Hall, N.G., Kamoun, H. and Sriskandarajah, C., "Scheduling in robotic cells: Complexity and steady state analysis", Working Paper 93-55, College of Business, The Ohio State University, 1993.
Hall, N.G., Potts, C.N. and Sriskandarajah, C., "Parallel machine scheduling with a common server", Working Paper 94-21, College of Business, The Ohio State University, 1994.
Hammer, P.L and Rader, D.J., "Efficient methods for solving quadratic 0-1 knapsack problems", Rutcor Research Report 40-94, Rutgers University, 1994, INFOR, to appear.
Hanen, C. and Munier, A., "Periodic scheduling of several hoists", in: Proc. Fourth International Conf. Project Management and Scheduling (1994) 108-110.
Hirabayashi, R., Suzuki, H. and Tsuchiya, N., "Optimal tool module design problem for NC machine tools", Jourrnal of the Operations Research Society of Japan 27 (1984) 205-228.
Hoffman, A.J., Kolen, A.W.J. and Sakarovitch, M., "Totally balanced and greedy matrices", SIAM Journal on Algebraic and Discrete Methods 6 (1985) 721-730.
Hwang, S., "A constraint-directed method to solve the part selection problem in flexible manufacturing systems planning stage", in: Stecke, K.E. and Suri, R. (eds.), Proc. of the Second ORSA / TIMS Conference on Flexible Manufacturing Systems, Elsevier Science Publishers B.V., Amsterdam, 1986, 297-309.
Hwang, S. and Shogan, A.W., "Modelling and solving an FMS part selection problem", International Journal of Production Research 27 (1989) 1349-1366.
loachim, I. and Soumis, F., "Schedule efficiency in a robotic production cell", International Journal of Flexible Manufacturing Systems 7 (1995) 5-26.
Jaikumar, R. and Van Wassenhove, L.N., "A production planning framework for flexible manufacturing systems", Journal of Manufacturing and Operations Management 2 (1989) 52-79.
Jeng, W.D., Lin, J.T. and Wen, U.P., "Algorithms for sequencing robot activities in a robot-centered parallelprocessor workcell", Computers and Operations Research 20 (1993) 185-197.
Johnson, E.L., Mehrotra, A. and Nemhauser, G.L., "Min-cut clustering", Mathematical Programming 62 (1993) 133-151.
Kamoun, H., Hall, N.G. and Sriskandarajah, C., "Scheduling in robotic cells: Heuristics and cell design", Management Science, submitted for publication.
Kats, V. and Levner, E., "The constrained cyclic robotic flowshop problem: A solvable case, in: E. Levner (ed.), Intelligent Scheduling of Robots and Flexible Manufacturing Systems, Center for Technological Education, Holon, Israel, 1995, 115-128.
King, J.R. and Nakornchai, V., "Machine component group formation in group technology: review and extension", International Journal of Production Research 20 (1982) 117-133.
King, R.E., Hodgson, T.J. and Chafee, F.W., "Robot task scheduling in a flexible manufacturing cell", IIE Transactions 25 (1993) 80-87.
Kise, H., "On an automated two-machine flowshop scheduling problem with infinite buffer", Journal of the Operations Research Society of Japan 34 (1991) 354-361.
Kise, H., Matsuo, H. and Sullivan, R.S., "Optimal cyclic scheduling for automated two-machine flowshops with no buffer", in: 1990 Japan - U.S.A. Symp. on Flexible Automation, ISCIE, Kyoto (1990), 1179-1185.
Kise, H., Shioyama, T. and Ibaraki, T., "Automated two machine flowshop scheduling: a solvable case", IIE Transactions 23 (1991) 10-16.
van de Klundert, J., Scheduling Problems in Automated Manufacturing, Doctoral Dissertation, University of Limburg, Maastricht, The Netherlands, 1996.
Kortsarz, G. and Peleg, D., "On choosing a dense subgraph", Extended abstract, Dept. of Applied Math, and Comp. Science, The Weizmann Institute, Rehovot, Israel, 1993.
Kou, L.T., "Polynomial complete consecutive information retrieval problems", SIAM Journal on Computing 6 (1977) 67-75.
Kouvelis, P., "Design and planning problems in flexible manufacturing systems: A critical review", Journal of Intelligent Manufacturing 3 (1992) 75-99.
Kouvelis, P. and Lee, H.L., "Block angular structures and the loading problem in flexible manufacturing systems", Operations Research 39 (1991) 666-676.
Kuhn, H., Einlastungsplanung von flexiblen Fertigungssystemen, Physica-Verlag, Heidelberg, 1990.
Kusiak, A., "Applications of operational models and techniques in flexible manufacturing systems", European Journal of Operational Research 24 (1986) 336-345.
van Laarhoven, P.J.M. and Zijm, W.H.M., "Production preparation and numerical control in PCB assembly", The International Journal of Flexible Manufacturing Systems 5 (1993) 187-207.
Lawler, E.L., Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys. D.B., "Sequencing and scheduling: Algorithms and complexity", in: S.C., Graves, A.H.G. Rinnooy Kan and P.H. Zipkin (eds.), Logistics of Production and Inventory, Elsevier Science Publishers, Amsterdam, 1993, 445-522.
Lei. L., "Determining the optimal starting times in a cyclic schedule with a given route", Computers and Operations Research 20 (1993) 807-816.
Lei, L. and Wang, T.J., "A proof: The cyclic hoist-scheduling problem is NP-complete", Working Paper 89-16, Graduate School of Management, Rutgers University, 1989.
Lei, L. and Wang, T.J., "The minimum common-cycle algorithm for cyclic scheduling of two material handling hoists with time window constraints", Management Science 37 (1991) 1629-1639.
Lei, L. and Wang, T.J., "On the optimal cyclic schedules of single hoist electroplating processes", IIE Transactions 26 (1994).
Lengauer, T., Combinatorial Algorithms for Integrated Circuit Layout, John Wiley and Sons Ltd., Chichester, 1990.
Levner. E., Kats, V. and Levit, V.E., "An improved algorithm for a cyclic robotic scheduling problem, in: E. Levner (ed.). Intelligent Scheduling of Robots and Flexible Manufacturing Systems, Center for Technological Education, Holon, Israel, 1995, 129-141.
Levner, E., Kogan, K. and Levin, I., "Scheduling a two-machine robotic-cell: A solvable case", Annals of Operations Research 57 (1995) 217-232.
Lieberman, R.W. and Turksen, I.B., "Crane scheduling problems", AIIE Transactions 13 (1981) 304-311.
Liu, S.-C. and Lin, L., "Dynamic sequencing of robot moves in a manufacturing cell", European Journal of Operational Research 69 (1993) 482-497.
Lofgren, C.B., McGinnis, L.F. and Tovey, C.A., "Routing printed circuit cards through an assembly cell", Operations Research 39 (1991) 992-1004.
Mamer, J.W. and Shogan, A.W., "A constrained capital budgeting problem with applications to repair kit selection", Management Science 33 (1987) 800-806.
Manier, M.-A., Varnier, C. and Baptiste. P., "A multi-hoists scheduling problem approach, in: Proc. Fourth International Conf. Project Management and Scheduling (1994) 110-115.
Mazzola, J.B., "Generalized assignment with nonlinear capacity interaction", Management Science 35 (1989) 923-941.
Mazzola, J.B., Neebe, A.W. and Dunn, C.V., "Production planning of a flexible manufacturing system in a material requirements planning environment", The International Journal of Flexible Manufacturing Systems 1 (1989) 115-142.
Mazzola, J.B. and Schantz, R.H., "Single-facility resource allocation under capacity-based economies and diseconomies of scope", Management Science 41 (1995) 669-689.
McCormick, W.T., Schweitzer, P.J. and White, T.W., "Problem decomposition and data reorganization by a clustering technique", Operations Research 20 (1972) 993-1009.
McGeoch, L.A. and Sleator, D.D., "A strongly competitive randomized paging algorithm", Algorithmica 6 (1991) 816-825.
Mohring, R.H., "Graph problems related to gate matrix layout and PLA folding, in: G. Tinhofer et al. (eds.), Computational Graph Theory, Springer-Verlag, Vienna, 1990, 17-51.
Moreno, A.A. and Ding, F.-Y., "Heuristics for the FMS-loading and part-type-selection problems", The International Journal of Flexible Manufacturing Systems 5 (1993) 287-300.
Nemhauser, G.L. and Wolsey, L.A., Integer and Combinatorial Optimization, John Wiley and Sons, New York, 1988.
Ng, W.C., "A branch-and-bound algorithm for hoist scheduling of a circuit board production line", International Journal of Flexible Manufacturing Systems 8 (1996) 45-65.
Oerlemans, A.G., "Flexible manufacturing: Concepts and methods", JORBEL - Belgian J. of Operations Research, Statistics and Computer Science 34 (1994) 5-22.
Phillips, L.W. and Linger, P.S., "Mathematical programming solution of a hoist scheduling program", AIIE Transactions 8 (1976) 219-225.
Privault, C., Modèles Mathématiques pour la Gestion Off-line et On-line des Changements d'Outils sur une Machine Flexible, Doctoral thesis, Université Joseph Fourier, Grenoble, 1994.
Privault, C. and Finke, G., "Tool management on NC-machines", in: Proc. Int. Conf. on Indust. Engineering and Prod. Management, Mons, Belgium, 1993, 667-676.
Rajagopalan, S., "Scheduling problems in flexible manufacturing systems", Working Paper, G.S.I.A., Carnegie-Mellon University. Pittsburgh, PA, 1985.
Rajagopalan, S., "Formulation and heuristic solutions for parts grouping and tool loading in flexible manufacturing systems", in: Stecke, K.E. and Suri, R. (eds.), Proc. of the Second ORSA / TIMS Conference on Flexible Manufacturing Systems, Elsevier Science Publishers, B.V., Amsterdam, 1986, 311-320.
Roger, C., La Gestion des Outils sur Machines a Commande Numérique, DEA thesis in Operations Research, Université Joseph Fourier, Grenoble, 1990.
Sethi, A.K. and Sethi, S.P., "Flexibility in manufacturing: A survey", The International Journal of Flexible Manufacturing Systems 2 (1990) 289-328.
Sethi, S.P., Sriskandarajah, C., Sorger, G., Blazewicz, J. and Kubiak, W., "Sequencing of parts and robot moves in a robotic cell", The International Journal of Flexible Manufacturing Systems 4 (1992) 331-358.
Shapiro, G.W. and Nuttle, H.L.W., "Hoist scheduling for a PCB electroplating facility", IIE Transactions 20 (1988) 157-167.
Sodhi, M.S., Agnetis, A. and Askin, R.G., "Tool addition strategies for flexible manufacturing systems", The International Journal of Flexible Manufacturing Systems 6 (1994) 287-310.
Solot, P. and Van Vliet, M., "Analytical models for FMS design optimization: A survey", The International Journal of Flexible Manufacturing Systems 6 (1994) 209-233.
Sriskandarajah, C., Hall, N.G., Kamoun, H. and Wan, H., "Scheduling large robotic cells", Working Paper, College of Business, The Ohio State University, 1994.
Sriskandarajah, C. and Ladet, P., "Some no-wait shops scheduling problems: Complexity aspect", European Journal of Operational Research 24 (1986) 424-438.
Sriskandarajah, C. and Sethi, S.P., "Scheduling algorithms for flexible flowshops: Worst and average case performance", European Journal of Operational Research 43 (1989) 143-160.
Stecke, K.E., "Formulation and solution of nonlinear integer production planning problems for flexible manufacturing systems", Management Science 29 (1983) 273-288.
Stecke. K.E., "Algorithms for efficient planning and operations of a particular FMS", The International Journal of Flexible Manufacturing Systems 1 (1989) 287-324.
Stecke. K.E. and Kim, I., "A study of part type selection approaches for short-term production planning", The International Journal of Flexible Manufacturing System 1 (1988) 7-29.
Stecke, K.E. and Talbot, F.B., "Heuristics for loading flexible manufacturing systems", in: A. Raouf and S.I. Ahmad (eds.), Flexible Manufacturing: Recent Developments in FMS, Robotics, CAD/CAM. CIM, Elsevier, Amsterdam, 1985, 73-85.
Tang, C.S. and Denardo, E.V., "Models arising from a flexible manufacturing machine, Part I: Minimization of the number of tool switches", Operations Research 36 (1988) 767-777.
Tang, C.S. and Denardo, E.V., "Models arising from a flexible manufacturing machine, Part II: Minimization of the number of switching instants", Operations Research 36 (1988) 778-784.
Tempelmeier, H. and Kuhn, H., "OR-Modelle zur Planung flexibler Fertigunssysteme", OR Spektrum 14 (1992) 177-192.
Tempelmeier, H. and Kuhn, H., Flexible Fertigungssysteme - Entscheidungsunterstützung für Konfiguration und Betrieb, Springer, Berlin, Heidelberg, 1992.
Van Looveren, AJ., Gelders, L.F. and Van Wassenhove, L.N., "A review of FMS planning models", in: A. Kusiak (ed.), Modelling and Design of Flexible Manufacturing Systems, Elsevier Science Publishers B.V., Amsterdam, 1986, 3-31.
Veeramani, D., Upton, D.M. and Barash, M.M., "Cutting-tool management in computer-integrated manufacturing", The International Journal of Flexible Manufacturing Systems 3/4 (1992) 237-265.
Weingartner, H.M., "Capital budgeting of interrelated projects: Survey and synthesis", Management Science 12 (1966) 485-516.
de Werra, D. and Widmer, M., "Loading problems with tool management in flexible manufacturing systems: A few integer programming models", The International Journal of Flexible Manufacturing Systems 3 (1990) 71-82.
Whitney, C.K. and Gaul, T.S., "Sequential decision procedures for batching and balancing in FMSs", Annals of Operations Research 3 (1985) 301-316.
Widmer, M., "Job shop scheduling with tooling constraints: A tabu search approach", Journal of the Operational Research Society 42 (1991) 75-82.
Wolsey, L.A., "MIP modeling of changeovers in production planning and scheduling problems", in: R. Slowinski (ed.), Semi-Plenary Papers - 14th European Conference on Operational Research, Poznan, Poland (1995) 197-210.