Batching and resource allocation decisions on an m-machine proportionate flowshop

Abstract

This article considers an m-machine proportionate flowshop scheduling problem where each stage of production consists of a batching operation. Moreover, we assume that the job processing times are controllable through the allocation of a non-renewable resource. The objective consists of minimising the makespan. The scheduler’s task consists of (1) allocating jobs to batches; (2) scheduling batches on the m-machine flowshop; (3) allocating resources to batches; and (4) allocating the resources within each batch to jobs. We show that there exists an optimal solution to the problem that consists of sequencing the jobs in Λ-shape order based on their workloads. Furthermore, the jobs that are sorted in non-decreasing order of workload are scheduled in batches of equal size, whereas the remaining jobs are allocated to batches of different sizes. We present an $O(n^2)$ time algorithm based on the observation that all jobs scheduled in the first segment of the Λ-shape have workloads that are smaller than (or equal to) that of the last job in the sequence.

Keywords:

• Proportionate flowshop
• batching
• makespan
• resource consumption function
• workload