Assembly job shop scheduling problems with component availability constraints.

Abstract

Job shop scheduling has been widely studied for several decades. In generalized of the job shop scheduling problem, n jobs are to be processed on m machines under specific routings and due dates. The majority of job shop scheduling research concentrates on manufacturing environments processing string-type jobs with a linear routing where no assembly operations are involved. However, many manufacturing environments produce complex products with multi-level assembly job structures and cannot be scheduled efficiently with existing job shop scheduling techniques. Little research has been done in the area of assembly job shop scheduling, and we are not aware any of those studies consider on the availability of purchased components and the impact of component availability on the performance of assembly job shops. This research focuses on scheduling job shops that process jobs requiring multiple-levels of assembly and it also considers the availability of components that are procured from outside suppliers. By considering material constraints during production scheduling, manufacturers can increase resource utilization and improve due date performance.

To represent assembly job shop scheduling problems with component availability constraints, a modified disjunctive graph formulation is developed in this research. A mixed-integer programming model with the objective of minimizing the total weighted-tardiness is also developed in this research. Several heuristic methods, described as modified shifting bottleneck procedure (MSBP), efficient shifting bottleneck procedure (ESBP) and rolling horizon procedure (RHP), are proposed to reduce the computational time required for assembly job shop scheduling problems. These methods are extended from the shifting bottleneck procedure. The performance of various flavors of the MSBP and ESBP is demonstrated on a set of test instances and compared with different dispatching rules that are widely used in practice. Results show that MSBP and ESBP outperform the dispatching rules by 18% to 16% on average.

This dissertation not only studies the assembly job shop scheduling problem with component availability constraints, but also demonstrates how the decomposition methodology can reduce the complexity of NP-hard problems. Based on the relative preference of solution quality and computational time, recommendations for appropriate methods to solve assembly job shop scheduling problems with different problem sizes are given in the conclusions of this dissertation.