Multiple orders per job scheduling problems

The standard unit of transfer in new 300-mm semiconductor wafer fabrication facilities is the front opening unified pod (FOUP). Due to automated material handling system concerns, the number of FOUPs in a wafer fab is kept limited. Moreover, a certain number of new and larger 300-mm wafers will be placed in these FOUPS and this makes grouping orders from multiple customers into jobs a necessity. Thereby, efficient utilization of FOUP capacity while attaining maximum on-time delivery is a challenge.; This dissertation investigates the multiple orders per job scheduling problem by first presenting a nonlinear mixed-integer program formulation that encompasses both order grouping and job scheduling decisions to minimize two different objectives individually: total weighted completion time and total weighted tardiness. Both objectives are minimized for a single machine environment subject to either single unit or single lot processing restrictions.; Recognizing the tractability limitations of this formulation, the problem is linearized so that it is solvable using standard mixed-integer programming solvers. A dispatching rule-based heuristic and multiple metaheuristic approaches are then proposed that solve problem instances much faster than the mathematical program for the single machine environment, as they are all based on optimality properties exhibited by multiple orders per job scheduling problems.; The second part of this dissertation discusses the development and application of metaheuristics in the multiple orders per job scheduling problem. Both Tabu Search and Genetic Algorithm approaches are studied with different result representations. Experimental results demonstrate the efficacy of the metaheuristic approaches for minimizing the performance objectives of interest in an acceptable amount of computation time.; As the multiple orders per job scheduling problem in single machine environment is much simpler than the realistic environment, the problem is then investigated in a much more complicated environment: parallel machines subject to sequence-dependent and sequence-independent setup times. This new problem not only involves order-to-job assignment and job scheduling decisions, but also requires job-to-machine assignment decisions and decisions pertaining to order sequencing within the jobs. Similar heuristic approaches are developed for this complex problem and are evaluated again in both single unit processing and single lot processing environments to minimize total weighted completion time and total weighted tardiness of orders individually.; The concept of virtual orders is implemented to assist the mathematical model in calculating setup times accurately by assigning each job position a product type. The idea of inserting virtual orders results in increased computing time due to the rapidly expanding number of constraints and variables. Experimental results demonstrate the difficulty of solving the problem using an optimization-based approach, demonstrating that heuristics can find a good solution to the problem in a reasonable amount of computation time.