One-machine Generalized Precedence Constrained Scheduling

We investigate one-machine scheduling problems subject to generalized prece-dence constraints. A precedence constraint specifies that the first of a pair of jobs must be completed before the second can begin. Under our generalized notion, not only must the first job be completed before the second can begin, but also, the dif-ference between the start time of the second job and the completion time of the first job must fall in a given pair-dependent interval. The left endpoint of this interval, if greater than zero, specifies a minimum delay and the right endpoint, if finite, specifies a maximum delay between the two jobs. To our knowledge, this dissertation contains the first explicit identification of generalized precedence constraints as we have defined them. As such, it represents the first systematic treatment of generalized precedence constrained scheduling. Our major emphases include drawing the line between easy and hard problems with respect to precedence constraint type, precedence relation, and optimality cri-terion and identifying suitable algorithms and finding effective heuristics for prob-lems that are easy and hard, respectively. We consider minimizing makespan, tota