On the complexity of preemptive openshop scheduling problems Academic Article uri icon

abstract

  • We investigate the complexity status of the preemptive openshop scheduling problem. After reviewing recent studies of the shop with various objective functions, we define the concept of preempting job w.r. to a schedule, and state some general results for the preemptive openshop environment. These results are then used to show by reduction from the 3-Partition, that the n job-2 machine mean flow time problem with ready times and job preemption is unary NP-hard. 1994.

published proceedings

  • European Journal of Operational Research

author list (cited authors)

  • Sriskandarajah, C., & Wagneur, E.

citation count

  • 3

complete list of authors

  • Sriskandarajah, C||Wagneur, E

publication date

  • September 1994