One Machine Generalized Precedence Constrained Scheduling.

摘要

We investigate one-machine scheduling problems subject to generalized precedence 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 difference 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.