A BRANCH AND BOUND PROCEDURE FOR SETUP PROBLEMS IN FLEXIBLE MANUFACTURING SYSTEMS

Abstract

We address a medium‐ to short‐term production planning problem in a flexible manufacturing environment. First we present a single‐machine, mixed integer programming model for part type selection and lot‐sizing problems over a T‐period planning horizon. Demand for part types changes dynamically through the periods. The objective is to meet the demand for part types during the periods they are demanded. Available machine time and tool magazine capacities are the system constraints in our models. We next extend on the single‐ machine model to include multiple machines. In addition to part type selection and lotsizing decisions, the extended model also addresses the machine‐loading decision. We present exact branch and bound procedures based on linear programming relaxations for the two models. We also report the results of our computational experiments.

Keywords

FLEXIBLE MANUFACTURING SYSTEMS PART TYPE SELECTION MACHINE‐LOADING MIXED INTEGER PROGRAMMING BRANCH AND BOUND

Get full access to this article

View all access options for this article.

References

Afentakis

(1986), “Maximum Throughput in Flexible Manufacturing Systems” in Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Stecke

K. E.

and Suri

(eds.), Elsevier Science Publishers, Amsterdam, 509–521.

Berrada

and Stecke

K. E.

(1986), “A Branch and Bound Procedure for Machine Load Balancing in Flexible Manufacturing Systems,” Management Science, 32, 10, 1316–1335.

Bitran

G. R.

and Matsuo

(1986), “The Multi‐Item Capacitated Lot Size Problem: Error Bounds of Manne's Formulation,” Management Science, 32, 3, 350–359.

Chakravarty

A. K.

and Shtub

(1984), “Selecting Parts and Loading Flexible Manufacturing Systems,” in Proceedings of the First ORSA/TIMS Special Interest Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Stecke

K. E.

and Suri

(eds.), Elsevier Science Publishers, Amsterdam, 284–289.

Chakravarty

A. K.

(1986), “Production Planning with Flexibilities in Capacity” in Proceedings of the Second ORSA/TIMS Special Interest Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Stecke

K. E.

and Suri

(eds.), Elsevier Science Publishers, Amsterdam, 333–343.

Chang

Y. L.

Sullivan

R. S.

Bagchi

, and Wilson

J. R.

(1985), “Experimental Investigation of Real‐Time Scheduling in Flexible Manufacturing Systems,” Annals of Operations Research, 3, 355–377.

Erschler

Roubellat

, and Thuriot

(1985), “Steady State Scheduling of a Flexible Manufacturing System with Periodic Releasing and Flow Time,” Annals of Operations Research, 3, 333–353.

Florian

Lenstra

J. K.

, and Rinnooy Kan

H. G.

(1980), “Deterministic Production Planning: Algorithms and Complexity,” Management Science, 26, 7, 12–20.

Hirabayashi

Suzuki

, and Tsuchiya

(1984), “Optimal Tool Module Design Problem for NC Machine Tools,” Journal of Operations Research Society of Japan, 27, 3, 205–228.

10.

Hutchinson

Leong

Snyder

, and Ward

(1989), “Scheduling for Random Job Shop Flexible Manufacturing Systems” in Proceedings of the Third ORSA/TIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Stecke

K. E.

and Suri

(eds.), Elsevier Science Publishers, Amsterdam, 127–132.

11.

Hwang

S. S.

(1986), “A Constraint‐Directed Method to Solve the Part Selection Problem in Flexible Manufacturing Systems Planning Stage” in Proceedings of the Second ORSA/TIMS Special Interest Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Stecke

K. E.

and Suri

(eds.), Elsevier Science Publishers, Amsterdam, 298–309.

12.

Hwang

S. S.

and Shogan

A. W.

(1989), “Modelling and Solving an FMS Part Type Selection Problem,” International Journal of Production Research, 27, 8, 1349–1366.

13.

Jaikumar

and Van Luk

N. Wassenhove

(1986), A Production Planning Framework for Flexible Manufacturing Systems, Working Paper, Harvard Business School, Boston, MA.

14.

Kim

Y.‐D.

and Yano

C. A.

(1989), An Iterative Approach to System Setup Problem in Flexible Manufacturing Systems, Technical Report 89–7, Dept. of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, MI.

15.

Kiran

A. S.

(1986), Complexity of the FMS Loading and Scheduling Problems, Working Paper, Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA.

16.

Kiran

A. S.

and Tansel

B. C.

(1986), “The System Setup in FMS: Concepts and Formulation” in Proceedings of the Second ORSA/TIMS Special Interest Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Stecke

K. E.

and Suri

(eds.), Elsevier Science Publishers, Amsterdam, 321–332.

17.

Kusiak

(1985), “Part Families Selection Model for Flexible Manufacturing Systems,” Annals of Operations Research, 3, 279–300.

18.

Kusiak

(1986), “Application of Operational Research Models and Techniques in Flexible Manufacturing,” European Journal of Operations Research, 24, 336–345.

19.

Rajagopalan

(1986), “Formulation and Heuristic Solution for Parts Grouping and Tool Loading in Flexible Manufacturing Systems” in Proceedings of the Second ORSA/TIMS Special Interest Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Stecke

K. E.

and Suri

(eds.), Elsevier Science Publishers, Amsterdam, 331–320.

20.

Shanker

and Tzen

Y. J.

(1985), “A Loading and Dispatching Problem in a Random Flexible Manufacturing System,” International Journal of Production Research, 23, 3, 579–595.

21.

Smith

M. L.

Ramesh

Dudek

R. A.

, and Blair

E. L.

(1986), “Characteristics of U.S. Flexible Manufacturing Systems: A Survey” in Proceedings of the Second ORSA/TIMS Special Interest Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Stecke

K. E.

and Suri

(eds.), Elsevier Science Publishers, Amsterdam, 478–486.

22.

Stecke

K. E.

(1983), “Formulation and Solution of Nonlinear Integer Production Planning Problems for Flexible Manufacturing Systems,” Management Science, 29, 3, 273–288.

23.

Stecke

K. E.

(1986), “A Hierarchical Approach to Solving Machine Grouping and Loading Problems of Flexible Manufacturing Systems,” European Journal of Operations Research, 24, 369–378.

24.

Stecke

K. E.

(1988), “Algorithms to Efficiently Plan and Operate a Particular FMS,” Working Paper No. 566, School of Business Administration, The University of Michigan, Ann Arbor, MI.

25.

Stecke

K. E.

and Kim

(1988), “A Study of FMS Part Type Selection Approaches for Short‐Term Production Planning,” International Journal of Flexible Manufacturing Systems, 1, 7–29.

26.

Tang

C. S.

and Denardo

E. V.

(1988), “Models Arising form a Flexible Manufacturing Machine, Part 1: Minimization of the Number of Tool Switches,” Operations Research, 35, 5, 767–777.