Formulation and Solution of Nonlinear Integer Production Planning Problems for Flexible Manufacturing Systems

A flexible manufacturing system (FMS) is an integrated, computer-controlled complex of automated material handling devices and numerically controlled machine tools that can simultaneously process medium-sized volumes of a variety of part types. FMSs are becoming an attractive substitute for the conventional means of batch manufacturing, especially in the metal-cutting industry. This new production technology has been designed to attain the efficiency of well-balanced, machine-paced transfer lines, while utilizing the flexibility that job shops have to simultaneously machine multiple part types. Some properties and constraints of these systems are similar to those of flow and job shops, while others are different. This technology creates the need to develop new and appropriate planning and control procedures that take advantage of the system's capabilities for higher production rates. This paper defines a set of five production planning problems that must be solved for efficient use of an FMS, and addresses specifically the grouping and loading problems. These two problems are first formulated in detail as nonlinear 0-1 mixed integer programs. In an effort to develop solution methodologies for these two planning problems, several linearization methods are examined and applied to data from an existing FMS. To decrease computational time, the constraint size of the linearized integer problems is reduced according to various methods. Several real world problems are solved in very reasonable time using the linearization that results in the fewest additional constraints and/or variables. The problem characteristics that determine which linearization to use, and the application of the linearized models in the solution of actual planning problems, are also discussed.