Genetic programming-based hyper-heuristic approach for solving dynamic job shop scheduling problem with extended technical precedence constraints

摘要

Extended technical precedence constraints (ETPC) in dynamic job shop scheduling problem (DJSP) are the precedence constraints existing between different jobs instead of the conventional technical precedence constraints existing in the operations of the same job. This paper presents the mathematical programming model of the DJSP with ETPC to minimize the mean weighted tardiness of the jobs. The mathematical model contributes to the solution and modelling of the DJSP with ETPC and it is used to solve small-sized problems to optimality. To solve industry-sized problems, a constructive heuristic called the dispatching rule (DR) is employed. This paper investigates the use of genetic programming (GP) as a hyper-heuristic in the automated generation of the problem-specific DRs for solving the problem under consideration. The genetic programming-based hyper heuristic (GPHH) approach constructs the DRs which are learned from the training instances and then verified on the test instances by the simulation experiments. To enhance the efficiency of the approach when evolving effective DRs to solve the problem, the approach is improved with strategies which consist of a problem-specific attribute selection for GP and a threshold condition mechanism for fitness evaluation. The simulation results verify the effectiveness and efficiency of the evolved DRs to the problem under consideration by comparing against the existing classical DRs. The statistical analysis of the simulation results shows that the evolved DRs outperform the selected benchmark DRs on the problem under study. The sensitivity analysis also shows that the DRs generated by the GPHH approach are robust under different scheduling performance measures. Moreover, the effects of the model parameters, including the percentage of jobs with ETPC and the machine utilization, on the performance of the DRs are investigated.