Multi-routed job shop scheduling

Abstract

The research presented in this thesis is concerned with scheduling n jobs in an m work center job shop facility. The objective in this research was to develop scheduling methodologies which optimally or sub-optimally schedule n jobs on m work centers in a job shop or a Flexible Manufacturing System (FMS) environment, where the jobs have multiple possible routings and the work centers have varying efficiencies depending on the routing. The schedules generated address three performance measures: work center utilization balancing, mean weighted flowtime, and makespan. The scheduling methodologies developed take into account the priority, or weightage factor, of the jobs. The dynamic nature of the facility has also been taken into consideration. Both optimal and sub-optimal solution procedures were developed in this research. Although Integer Programming Model #1 (IPM 1) is an optimal solution seeking procedure, the computational complexity involved, given present-day computing capabilities, renders it functionally infeasible. Due to this reason, three sub-optimal procedures, Integer Programming - Heuristic Model (IPM-H), Heuristic Procedure #1 (HP 1), and Heuristic Procedure #2 (HP 2) were developed. IPM 1 and JPM-H schedule jobs in a static case, whereas HP 1 and HP 2 schedule in a dynamic environment. IPM 1 extends and improves upon Manne's integer programming model developed to solve the general job shop problem [30]. It is an optimal scheduling procedure to solve the problem. IPM-H is a combination of an integer programming model and a heuristic procedure to solve the problem sub-optimally in a static environment. The integer programming stage of IPM-H optimally balances the workloads on the different work centers by selecting the alternate routes. The scheduling of the jobs once they have been assigned to the work centers is done by the heuristic stage of IPM-H, which is a modification of the Baker's heuristic [1]. HP 1 is a procedure which iteratively selects and loads the alternate routes on the work centers while trying to attain balanced work center utilizations. HP 2 tries to balance the work center utilizations by loading jobs along all the alternate routes and progressively unloading those alternate routes of the jobs which occupy the maximum loaded work center. A simulation study was conducted using a 10 work center job shop with 10 to 100 jobs to test the efficiency of the heuristic solution procedures. Out of the three suboptimal procedures, HP 1 gave the most desirable results and so is recommended. IPM-H and HP 2 gave sufficiently good results for job shops that are loaded to the capacity.