Unrelated parallel machine scheduling with sequence-dependent setup times and machine eligibility restrictions for minimizing the makespan

In the current competitive environment, effective sequencing and scheduling has become a necessity for survival in the market place. In this dissertation, a scheduling problem that arises from a real situation involving roof truss manufacturing at the MiTek Corporation is considered.;The main objective of this research is to develop a heuristic algorithm to find a good, quick solution to the unrelated parallel machine problem with sequence-dependent setup times and machine eligibility restrictions where the objective is to minimize the time required to complete all jobs, i.e., the makespan.;The presence of sequence-dependent setup times significantly increases the difficulty of scheduling jobs to parallel machines with different processing times. The addition of machine eligibility restrictions further complicates the scheduling process. Although, sequence-dependent setup times and machine eligibility restrictions are a common occurrence, there has been little empirical work to evaluate heuristics for this domain. In this research, heuristic algorithms for approaching this problem have been developed. Specifically, four algorithms have been developed to minimize the makespan on four different classes of unrelated parallel machine scheduling problems. The first algorithm, the partitioning heuristic, addressed the first elementary class of problems that includes neither setup times nor machine eligibility restrictions. The second algorithm, the partitioning with machine eligibility heuristic, considered the machine eligibility restrictions and ignored the setup times. The third algorithm, the partitioning-estimation heuristic, considered the setup times and ignored the machine eligibility restrictions. Finally, the fourth algorithm, the partitioning-estimation with machine eligibility heuristic, considered both the setup times and the machine eligibility restrictions.;In general, the algorithms used a constructive heuristic to assign jobs to machines followed by an improvement heuristic to enhance the solution. To assign jobs to machines and to improve the solution, the proposed algorithms incorporated two concepts. The first concept is modeled based on a procedure used by Salhi and Sari (1997) to solve the multi-depot vehicle routing problem (MDVRP) by making an initial assignment of selected jobs and then assigning the remaining (pending) jobs. The second concept is similar to the method used by Lee, Bhaskaran, and Pinedo (1997) to estimate the value of the makespan for the problem of scheduling jobs on a single machine with sequence-dependent setup times. The estimated makespan was used in assigning the pending jobs and in improving the solution for the problems that involve sequence-dependent setup times.;To evaluate the performance of the proposed algorithms, the makespan values based on the heuristic solutions were compared to optimal makespan values for test problems where they could be computed and to lower bounds otherwise. The results showed that the proposed heuristic algorithms could yield solutions within a few percent of the optimal solutions and lower bound solutions.;This research establishes some basic results for unrelated parallel machine scheduling problems and provides a foundation for addressing more practical scheduling problems in the area of unrelated machine scheduling.