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

abstract

  • 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.

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||De Velde, Steef Van

publication date

  • November 1997