| Popis: |
We consider the problem of scheduling n jobs in a pallet-constrained flowshop so as to minimize the makespan. In such a flowshop environment, each job needs a pallet the entire time, from the start of its first operation until the completion of the last operation, and the number of pallets in the shop at any given time is limited by a positive integer K \leq n. We focus primarily on the two-machine flowshop and specifically on the impact of the number of pallets on the makespan. While it is an NP-hard problem to find the minimum number of pallets subject to an upper bound on the makespan, we prove a worst-case bound on the minimum K that guarantees the least possible makespan. Furthermore, we investigate the empirical performance of Johnson's algorithm, which solves the problem to optimality if K \geq n, and Gilmore-Gomory's algorithm, which solves the problem to optimality if K = 2, when they are both straightforwardly adapted to deal with the situation where there are only K pallets available at any time, with 2 |
