A performance evaluation of permutation vs. non-permutation schedules in a flowshop

Abstract

It has been pointed out that a permutation schedule can be improved by a non-permutation schedule in a flowshop with completion-time based criteria, but there is a lack of comprehensive analyses. This paper presents an extensive computational investigation concerning the performance comparison between permutation and non-permutation schedules. The computational results indicate that in general, there is little improvement made by non-permutation schedules over permutation schedules with respect to completion-time based criteria. But the improvement is significant with respect to due-date based criteria, including total tardiness and total weighted tardiness. The results provide practitioners a guideline as to when to adopt a non-permutation schedule, which may exhibit better performance but require additional computational and control efforts.

Keywords:

• Scheduling
• Flowshop
• Non-permutation schedules