Parallel machine scheduling with specified release dates, due dates, and machine eligibility restrictions for minimizing makespan and maximum lateness

In this research, a problem that arises from a semiconductor manufacturing process is considered. Effective heuristic algorithms for scheduling n jobs on m parallel machines, with the objectives of minimizing maximum makespan, or minimizing maximum lateness when due dates are specified, have been developed. The processing characteristics considered are release dates, due dates, and machine eligibility restrictions.; The Least Flexible Job (LFJ), Longest Processing Time (LPT), Shortest Processing Time (SPT), and Earliest Due Date (EDD) rules were considered for job selection, and the Least Flexible Machine (LFM) rule for machine selection. An extensive analysis for determining the best order and combination of rules for each objective has been conducted. It was found that the order of scheduling jobs first or machines first, had no effect on the results. For the objective of minimizing makespan, the LPT rule was identified as the best rule for job selection. Combining this rule with other job selection rules did not improve the results. For the objective of minimizing maximum lateness, it was found that for job selection the EDD rule, and the LFJ/EDD and LFJ/SPT combination of rules performed equivalently.; In the literature, results for a problem with machine eligibility restrictions show that the LFJ rule is optimal for the objective of minimizing makespan; however, it requires the machine eligibility sets to be nested. This is seldom the case in practice. Therefore, two nesting conditions have been considered in this research, almost and poorly nested. It was found that the results are not affected by degree of nesting.; The effect of the having different due date characteristics was also analyzed. It was found that having slack or tight due dates does not affect the performance of the heuristics, and that the rules that perform best under slack due dates, also perform best for tight due dates.; The heuristics have been evaluated using real data from the Wafer Test Operations at Lucent Technologies. Comparisons have been made against the current scheduling system. This work develops a procedure that provides good solutions and that is feasible to integrate into the system for improvement.