Scheduling problems on a new setting of flexible flowshops: ℓ-Machine proportionate flowshops

Abstract

The classical flexible flowshop ($\mathit{FFc}$) environment consists of $c$-stages in series with $m$-machines in parallel at each stage, where each job has to undergo a particular series of actions. In this paper we consider a similar, yet different, and still a challenging real-life setting, that, to the best of our knowledge, has not been studied to date. We assume that there are $\ell$-sets in parallel in which each of the sets is an $m$-machine proportionate flowshop. In this new setting, each job can be processed on each one of the sets, but once a set is chosen, the job must be processed on all of its machines, in first-in-first-out method. We study several fundamental scheduling measures such as makespan, maximum tardiness with common due-date, total tardiness with common due-date, and total load. Moreover, we consider optional job-rejection and focus on minimising the total completion time. All problems are shown to be NP-hard, and pseudo-polynomial dynamic programming (DP) solution algorithms and Simulated Annealing (SA) metaheuristics are provided. The efficiency of all our proposed algorithms is validated through an extensive numerical study.

Keywords:

• Scheduling
• flexible proportionate flowshop
• regular performance measures
• dynamic programming
• simulated annealing

Disclosure statement

No potential conflict of interest was reported by the authors.