A MATHEMATICAL PROGRAMMING APPROACH FOR ROUTING AND SCHEDULING FLEXIBLE MANUFACTURING CELLS

Open Access
Author:
Pitts, Jr., Richard A
Graduate Program:
Industrial Engineering
Degree:
Doctor of Philosophy
Document Type:
Dissertation
Date of Defense:
June 28, 2006
Committee Members:
  • Jose Antonio Ventura, Committee Chair
  • M Jeya Chandra, Committee Member
  • Timothy William Simpson, Committee Member
  • Irene Johnston Petrick, Committee Member
Keywords:
  • flexible manufacturing cells
  • mixed-integer linear programming
  • tabu search meta-heuristic
  • scheduling
Abstract:
Scheduling of resources and tasks has been a key focus of manufacturing-related problems for many years. With increased competition in the global marketplace, manufacturers are faced with reduced profit margins and the need to increase productivity. One way to meet this need is to implement a flexible manufacturing system (FMS). A FMS is designed such that the efficiency of mass production is achieved while the flexibility of low-volume production is maintained. One type of FMS is the flexible manufacturing cell (FMC), which consists of a group of CNC machines and one material handling device. Scheduling is an important aspect in the overall control of the FMC. This research focuses on production routing and scheduling of jobs within a FMC. The major objective is to develop a methodology that minimizes the manufacturing makespan, which is the maximum completion time of all jobs. Due to the complexity of the FMC routing and scheduling problem, a 0-1 mixed-integer linear programming (MILP) model is formulated for M-machines and N-jobs with alternative routings. Although small instances of the problem can be solved optimally with a commercial optimization software package, a two-stage algorithm is proposed to solve medium-to-large-scale problems more efficiently. This two-stage algorithm utilizes two heuristics to generate an initial feasible sequence and an initial makespan solution during the construction Stage I. Then, during the improvement Stage II, the resulting initial solutions acquired from Stage I are combined with a Tabu Search meta-heuristic procedure. Within the Tabu Search procedure, an efficient pairwise interchange (PI) method and a linear programming (LP) subproblem are used to acquire improved solutions. The mathematical model and the proposed two-stage algorithm are demonstrated on several test problems for the makespan performance measure. Although the proposed algorithm does not achieve optimal solutions for every instance, the computational test results show that the algorithm is very effective in solving small, medium, and large size FMC scheduling problems. Overall, the proposed two-stage algorithm provides a tremendous savings in computational time compared to the exact MILP models and could be used in a true FMC environment with real-time scheduling situations.