Hybrid flow shop scheduling with several users

Abstract

Schedules have implications that are experienced collectively by a number of different persons with different responsibilities. It is, therefore, reasonable to make scheduling decisions in such a way that satisfies the considerations of all the involved partners. Unfortunately, even though there is a vast body of literature on production scheduling, the existing research generally concentrates on generating schedules that optimize one or more performance measures and does not address the problem of how to find a schedule that can be found acceptable by several users. Moreover, the considerations of the users may not be fully known in advance, can be implicit or qualitative, and therefore may not be included in the initial problem definition. In this study, we tackle with this problem and propose an approach that aims at determining a schedule that is the result of an agreement between different partners rather than at imposing an optimal solution to everyone. To alleviate difficulties, we suggest that it is first necessary to find a set of different schedules that can be considered efficient by everyone. The solutions can afterwards be passed on to the users to decide on the most appropriate schedule according to their priorities. The proposed two-step approach is illustrated on a hybrid flow shop environment. We propose a multimodal genetic algorithm to solve the first sub-problem. Our computational experiments on a set of benchmark problems from the literature indicate not only that the proposed algorithm is very competitive when compared to the existing exact or heuristic state-of-the-art methods, but that it is also quite promising in obtaining a diverse set of efficient (mostly optimal) alternative schedules. We address the second sub-problem using a multiplicative variant of the popular analytic hierarchy processing(AHP) technique, which does not suffer from dependence on irrelevant alternatives as the original version.