An approach to solve scheduling problems with atrributes assoaciated to the activities

Abstract

This paper shows an algorithm to deal with a scheduling problem that requires to deal with conditions related to the selections of activities and preferences for the selection of resources. The scheduling problem could be initially thought as a Flow Shop Scheduling (a particular case of a Job Shop Scheduling) [French,82]. The main difference respect to a Flow Shop Scheduling is that in our problem each activity does not require a (specified) machine but rather a member of a (specified) group of machines. Roughly speaking, we could say that discrete resources have to be considered instead of unary resources [OPL,99] [I,Sch-R,99], (many machines with identical characteristics to perform each process instead of just one machine for each process). Nevertheless, the output must specify the particular machine used by each activity and therefore the machines with identical characteristics have to be distinguished and as a result, sets of alternative resources have to be used instead of discrete resources [I,Sch-R,99]. The scheduling problem to be solved consist of n jobs to be performed using m groups of machines. Each job is described as a list of m activities of given processing times, to be executed in that order. Each activity uses a member of the associated group of machines. For each group of machines, there is a list of attributes. Each activity that uses a member of the corresponding group has values defined for each one of the attributes. Besides, there is a list of conditions associated to each attribute. Depending on the values of the attributes associated to the activities, the conditions will be fulfilled or unfulfilled. Formally, the conditions are defined as a function of the values of the attributes of the involved activities. In addition, the convenience of selecting a particular machine depends on the values of the attributes of the activity to be scheduled. The problem is to assign each activity to a starting time and to a specific machine, trying to verify the conditions aforementioned on one hand, and selecting machines according to the values of the attributes of the activities on the other hand. Finally, conditions (related to the selection of activities) and conveniences (for selecting machines) have associated weighs. This work shows an algorithm to select activities and machines taking into account these weighs.