System setup and scheduling problems in flexible manufacturing systems with partially grouped machines

Abstract

This dissertation focuses on system setup and scheduling problems with the overall objective of meeting due dates in flexible manufacturing systems (FMSs). In general, the system setup problem is concerned with decisions that have to be made before the FMS begins to produce parts, while the scheduling problem is concerned with running the FMS once it has been setup. In this dissertation, we consider multi-period order selection and loading problems for system setup, and a scheduling problem that results from these system setup problems, since other operational problems could be considered to be less critical than these problems. In general, system setup and scheduling problems are considered to be very critical, and hence solutions of these problem can play an important role in the operation of FMSs. The multi-period order selection problem is the problem of selecting orders to be produced in each period during the upcoming planning horizon with the objective of minimizing earliness and tardiness costs and subcontracting costs. The earliness and tardiness costs are incurred if an order is not finished on time, while subcontracting cost is incurred if an order is not selected within the planning horizon (and must be subcontracted) due to processing time capacity or tool magazine capacity. This problem is formulated as a 0-1 integer program which can be transformed into a generalized assignment problem. To solve the order selection problem, a heuristic algorithm is developed using a Lagrangian relaxation technique, and effectiveness of the algorithm is tested on randomly generated problems. The FMS loading problem is the problem of allocating operations and associated cutting tools to machines for a given set of selected parts (orders). There may be different environments for the loading problem that result from three ways of grouping machines in an FMS, i.e., no grouping, partial grouping, and total grouping. In this dissertation, we focus on the loading probl...