Date of Award
5-2022
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Industrial Engineering
Committee Chair/Advisor
Dr. Kevin Taaffe
Committee Member
Dr. Mary Beth Kurz
Committee Member
Dr. Herve Kerivin
Committee Member
Dr. Tugce Isik
Abstract
In some applications like fabric dying, semiconductor wafer processing, and flexible manufacturing, the machines being used to process jobs must be set up and serviced frequently. These setup processes and associated setup times between jobs often depend on the jobs and the sequence in which jobs are placed onto machines. That is, the scheduling of jobs on machines must account for the sequence-dependent setup times as well. These setup times can be a major factor in operational costs. In fabric dyeing processes, the sequence in which jobs are processed is also important for quality, i.e., there is a strong preference to run a certain type of job after another. There are also preferences associated with scheduling jobs on specific machines. Along with these preferences, there are also sequence-dependent restrictions, i.e., certain jobs are not allowed to immediately follow certain others on the same machine. In this dissertation, a mixed-integer linear programming (MILP) formulation is first developed to schedule jobs onto the machines while accounting for the setup times and the sequence-dependent restrictions. The newly introduced preferences have been modeled as two new objectives along with traditionally used objectives such as makespan, lateness, and total setup times. This MILP is found to be inadequate in solving some of the objectives. So, improvements are made to this formulation in the form of the addition of valid inequalities and solving some underlying separation problems to obtain tighter bounds. The different versions of the MILPs are compared for computational times and optimality gaps obtained on the multiple objectives. The improved MILPs perform significantly better on all objectives and hence are more usable as well. But, they also are found to be useful only for a certain level of problem sizes, beyond which their ability to obtain optimal solutions is severely hampered by the curse of dimensionality. To tackle larger problems, multiple construction heuristics have been developed/ adapted from literature. Some of these heuristics are basic job-placement rules like SPT (Shortest processing time) or EDD (earliest due date) which have been modified to handle the sequence-based restrictions and machine eligibility rules. Other construction heuristics have been developed to incorporate the newly introduced preferences. Next, a problem size breakdown method has been developed. This heuristic method incorporates a MILP to remove the fewest possible edges in the machine eligibility graph so that a larger problem can be broken down into independently solvable smaller problems solved to optimality. These heuristic methods are compared against the optimal solutions for small problems for solution quality on all five objectives. They are also compared against each other for larger problems. The MILP-based heuristic is also tested for computational performance. From the comparison results, it was seen that the methods developed so far are unable to tackle all the objectives simultaneously, and produce multiple solutions so that the user can evaluate trade-offs among the objectives. So, two popular multi-objective meta-heuristic frameworks have been adapted to tackle the new objectives as well as provide multiple Pareto-optimal solutions. Within each of the two methods, the job placement has been performed by two approaches: a construction heuristic approach and a semi-optimal approach. The two methods along with the two job placement approaches have been compared for computation times and quality of results. The best meta-heuristic methods are found to perform better than the construction heuristics on almost all objectives consistently, at the expense of more computational effort.
Recommended Citation
Srinath, Nitin, "A Study of Scheduling Problems with Sequence Dependent Restrictions and Preferences" (2022). All Dissertations. 3007.
https://open.clemson.edu/all_dissertations/3007