A Genetic Programming based Deep Reinforcement Learning Approach for Dynamic Hybrid Flow Shop Scheduling with Reworks under General Queue Time Limits

Abstract

This study addresses a dynamic hybrid flow shop scheduling in which each job that arrives dynamically must be reworked after a rework setup operation is done on a rework setup station if the queue time of the job between two arbitrary, not always successive, stages exceeds an upper limit. The problem is to determine the allocations of jobs to machines at each stage and the start times of jobs and rework setup/operations if occurred for the objective of minimizing the total tardiness. The problem is formulated as a mixed integer programming model. Then, a genetic programming based deep reinforcement learning solution approach is proposed that consists of two phases: (a) generate a set of hyper priority rules automatically using a variable neighborhood search based genetic programming algorithm; and (b) select a rule to cope with the system state at each scheduling point using the deep Q-network with state features, actions and rewards that reflect the characteristics of the problem. To test the performance of the solution approach, simulation experiments were done on various test instances, and the results show that the solution approach proposed in this study outperforms the conventional priority rule based one. The performance of the hyper priority rules generated by the genetic programming algorithm is also reported.