Heuristics for multiple orders per job scheduling problems

Production scheduling in semiconductor manufacturing involves a great amount of complexity. The current trend of replacing 200-mm diameter semiconductor wafers with a 300-mm diameter wafer adds an extra layer of complexity to wafer fabrication in semiconductor manufacturing. As a result of this transition, air sealed containers called FOUPs are used for safe handling and transporting the wafers between the workstations. Different customer's orders, in terms of integrated circuits (ICs) with order specific characteristics (size, ready time, importance) are converted into equivalent number of silicon wafers. Wafers corresponding to different orders may be assigned to the same FOUP while processing---this is known as a multiple orders per job ( moj) scheduling problem in the literature. The semiconductor manufacturing process involves assignment of orders to FOUPs, assignment of FOUPs to batches, and then scheduling of batches on single/multiple identical machines in a tool group. A wafer visits multiple tool groups during different stages of processing and also can visit a tool group multiple times before completing the manufacturing process (i.e., re-entrant flow). In this dissertation research, a lot processing environment is investigated, where the processing time of a job/FOUP is independent of the number of its contents.; In this dissertation, the moj scheduling problem is considered. The orders are assigned to FOUPs and the FOUPs are scheduled on the single/multiple machines. At first, a column generation (CG) approach is presented with an objective of minimizing the makespan of the orders while processing the FOUPs on a single machine. Later, the CG heuristic is extended to investigate the problem of minimizing the weighted completion time of the orders in a single and parallel machines environment. These CG heuristics are able to obtain near optimal solutions and also outperform the solution approaches presented in the literature.; This research is extended to address the moj complex job shop scheduling problem (moj-CJSSP) with an objective of minimizing the total weighted completion time of the orders. A two stage network based MIP is formulated to address the moj-CJSSP, where the first and second stages correspond to the development of the network and then formulate the moj-CJSSP problem based on the network, respectively. A CG heuristic is developed using the network structure from the MIP as a sub problem. Column generation heuristic obtains solutions very close to the MIP heuristic in problem instances with zero order ready times. A lower bound estimation approach is presented to compare the performances of the presented MIP heuristics and the CG approach.; With an effort to improve the performance of heuristics in solving problem instances with non-zero ready times, hybrid heuristics are developed. The initial hybrid heuristic (CP-ACO) includes a constraint programming (CP) model and an ant colony optimization (ACO). This CP-ACO heuristic resulted in a significant improvement in the solution quality, compared to the CG approach, especially in the problem instances with non-zero order ready times. Later, a hybrid heuristic (CP-MIP) involving the CP and the MIP is presented. This heuristic was able to marginally improve the solution quality compared to the MIP.