A mathematical programming approach for routing and scheduling flexible manufacturing cells.

摘要

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 a computer-controlled integrated manufacturing system with multi-functional computer numerically controlled (CNC) machines and a material handling system. The system 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 (e.g., robot, automated guided vehicle, conveyor, etc.). 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. The proposed methodology can also be extended to problems of minimizing the maximum tardiness and minimizing the absolute deviation of meeting due dates, among others.;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.