An algorithm to deal with due date violation in a multi-objective scheduling problem

Abstract

This paper includes part of the strategies used to solve a scheduling problem developed for a company that produces flexible packaging, presented in quite a 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 performs 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 (Ibañez et al., 2001). As mentioned there, some jobs could not be fulfilled to meet their due dates. An approach to decrease the quantity of due dates violations was presented in (Ibañez et al., 2002). The algorithm presented in (Ibañez et al., 2001) is entirely dedicated to verify as many conditions as possible disregarding due date violations. The algorithm shown in (Ibañez et al., 2002) was focussed to reduce the number of due date violations by paying the price of decreasing the fulfilment of conditions. Roughly speaking, the first approach favours the company whereas the second one is more convenient for the customers. The present work includes an algorithm, which allows us to assign weights to set an appropriate trade of between due date violation reduction and fulfillment of conditions.