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 ⩽ 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 ⩾ 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 avaiable at any time, with 2 < K < n. Our computational experiments with randomly generated instances reveal that for Johnson’s algorithm, which produces the least possible makespan, the required number of pallets to do so grows quite rapidly with the number of jobs. In contrast, Gilmore–Gomory’s algorithm, which may fail to produce the least possible makespan, requires consistently only about four pallets to produce schedules with a makespan very close to optimal.
