## Abstract

Preemptive scheduling in open shops and flow shops so as to minimize the mean flow time are both known to be strongly NP-hard on three or more machines. However, their complexity on two machines remained open for more than a decade. In this paper we show that open shop is NP-hard in the ordinary sense and flow shop is NP-hard in the strong sense. A linear time algorithm is also given to produce optimal schedules for two-machine open shops if the optimal order of completion times is known in advance. Finally, an O(N log N) time algorithm is given to produce optimal schedules for two-machine flow shops if the optimal order of completion times on the first machine is known in advance, where N is the number of jobs.

Original language | English (US) |
---|---|

Pages (from-to) | 24-44 |

Number of pages | 21 |

Journal | Journal of Algorithms |

Volume | 14 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1993 |

## All Science Journal Classification (ASJC) codes

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics