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

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.

authors

• Sriskandarajah, Chelliah

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

publisher

• Taylor & Francis  Publisher

published in

• INFOR: Information Systems and Operational Research  Journal

keywords

• Buffers
• Computational Complexity
• Flowshop Scheduling
• Makespan
• Pallets

Digital Object Identifier (DOI)

• 10.1080/03155986.1997.11732335

start page

• 277

end page

• 285

volume

• 35

issue

• 4