On the complexity of preemptive openshop scheduling problems Academic Article

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.

authors

• Sriskandarajah, Chelliah

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

publisher

• Elsevier  Publisher

published in

• European Journal of Operational Research  Journal

Digital Object Identifier (DOI)

• 10.1016/0377-2217(94)90406-5

start page

• 404

end page

• 414

volume

• 77

issue

• 3

URL

• http://dx.doi.org/10.1016/0377-2217(94)90406-5