Late work minimization in flow shops by a genetic algorithm

The work concerns the permutation flow shop scheduling problem with release times and the late work criterion. The late work criterion estimates the quality of a solution with regard to the duration of the late parts of jobs, not taking into account the quantity of the delay for the fully late activities. Particular jobs consist of a sequence of tasks, which have to be executed in the same order on a set of dedicated machines. The execution of a job has to start after its release time and it should finish preferably before its due date. Since the problem is known to be NP-hard, we propose a genetic algorithm to solve this scheduling case. We describe the components of the method, which is based on an indirect solution representation as a sequence of priority dispatching rules. A sequence of rules is transformed to a schedule by the list scheduling approach. Then, we report results of computational experiments, which were preceded by the tuning process of the genetic algorithm. Tests were performed for randomly generated instances of different difficulty in terms of the distribution of release times and due dates over time, as well as the number of jobs and machines. We analyze the results of computational experiments disclosing a strong influence of the problem data on the efficiency of the proposed meta-heuristic algorithm.