Assessing scheduling policies in a permutation flowshop with common due dates

Abstract

This paper focuses onto a situation arising in most real-life manufacturing environments when scheduling has to be performed periodically. In such a scenario, different scheduling policies can be adopted, being perhaps the most common to assume that, once a set of jobs has been scheduled, their schedule cannot be modified (‘frozen’ schedule). This implies that, when the next set of jobs is to be scheduled, the resources may not be fully available. Another option is assuming that the schedule of the previously scheduled jobs can be modified as long as it does not violate their due date, which has been already possibly committed to the customer. This policy leads to a so-called multi-agent scheduling problem. The goal of this paper is to discern when each policy is more suitable for the case of a permutation flowshop with common due dates. To do so, we carry out an extensive computational study in a test bed specifically designed to control the main factors affecting the policies, so we analyse the solution space of the underlying scheduling problems. The results indicate that, when the due date of the committed jobs is tight, the multi-agent approach does not pay off in view of the difficulty of finding feasible solutions. Moreover, in such cases, the policy of ‘freezing’ the schedule of the jobs leads to a very simple scheduling problem with many good/acceptable solutions. In contrast, when the due date has a medium/high slack, the multi-agent approach is substantially better. Nevertheless, in this latter case, in order to perceive the full advantage of this policy, powerful solution procedures have to be designed, as the structure of the solution space of the latter problem makes extremely hard to find optimal/good solutions.

Keywords:

• permutation flowshop
• scheduling

Acknowledgements

The authors are sincerely grateful to the anonymous referees.

Notes

This research has been funded by the Spanish Ministry of Science and Innovation, under the project ‘SCORE’ with reference DPI2010-15573/DPI.