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

Created by W.Langdon from gp-bibliography.bib Revision:1.7630

@Article{FAN:2021:COR,

• author = "Huali Fan and Hegen Xiong and Mark Goh",
• title = "Genetic programming-based hyper-heuristic approach for solving dynamic job shop scheduling problem with extended technical precedence constraints",
• journal = "Computer \& Operations Research",
• volume = "134",
• pages = "105401",
• year = "2021",
• month = oct,
• keywords = "genetic algorithms, genetic programming, Dynamic job shop scheduling, Dispatching rules, Hyper-heuristic, Extended technical precedence constraints",
• ISSN = "0305-0548",
• DOI = "doi:10.1016/j.cor.2021.105401",
• URL = "https://www.sciencedirect.com/science/article/pii/S0305054821001672",
• abstract = "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 load, on the performance of the DRs are investigated",

}

Genetic Programming entries for Huali Fan Hegen Xiong Mark Goh

Citations