Minimizing Makespan In Flowshops With Pallet Requirements: Computational Complexity Academic Article uri icon


  • We establish the computational complexity of the problem of minimizing makespan in a flowshop, where each jobs requires a pallet the entire time, from the start of its first operation until the completion of the last operation. We prove that the problem is NP-hard in the strong sense for m 2 and K 3, and for m 3 and K 2, where m is the number of machines and K is the number of pallets in the system.

published proceedings

  • INFOR Information Systems and Operational Research

author list (cited authors)

  • Wang, M., Sethi, S., Sriskandarajah, C., & Van De Velde, S.

citation count

  • 14

complete list of authors

  • Wang, Michael||Sethi, Suresh||Sriskandarajah, Chelliah||Van De Velde, Steef

publication date

  • November 1997