An algorithm for minimising due times violations in flexible package production scheduling

Abstract

This paper includes part of the strategies used to solve a scheduling problem developed for a company that produces flexible packaging, presented in a quite general form though. In this problem it is necessary to schedule several jobs that involve four process and for each one of them there is a group of machines available (of similar characteristics). Each activity is performed on just one machine. Besides, for our application, the scheduling must try to verify certain conditions. For each process (and consequently for all the activities that perform this process) there is a list of attributes. The problem is not only to assign each activity to a starting time and to a specific machine, but also to try to verify conditions that depend on the values of the attributes of the activities. Moreover, there are criteria to choose a particular machine. An approach to solve this problem was presented first in [1]. As mentioned there, some due dates could not be fulfilled on time. An approach to decrease the quantity of due dates violations was presented in [2 . This approach generates acceptable results for most of the cases in the real application. However, there were some cases in which the Algorithm did not work properly. The present work includes an Algorithm that improves the results generated in [2 ]for some special cases that arose in the real application.