摘要
For solving the job-shop scheduling problem (JSP), this paper proposes a novel two-level metaheuristic algorithm, where its upper-level algorithm controls the input parameters of its lower-level algorithm. The lower-level algorithm is a local search algorithm searching for an optimal JSP solution within a hybrid neighborhood structure. To generate each neighbor solution, the lower-level algorithm randomly uses one of two neighbor operators by a given probability. The upper-level algorithm is a population-based search algorithm developed for controlling the five input parameters of the lower-level algorithm, i.e., a perturbation operator, a scheduling direction, an ordered pair of two neighbor operators, a probability of selecting a neighbor operator, and a start solution-representing permutation. Many operators are proposed in this paper as options for the perturbation and neighbor operators. Under the control of the upper-level algorithm, the lower-level algorithm can be evolved in its input-parameter values and neighborhood structure. Moreover, with the perturbation operator and the start solution-representing permutation controlled, the two-level metaheuristic algorithm performs like a multistart iterated local search algorithm. The experiment's results indicated that the two-level metaheuristic algorithm outperformed its previous variant and the two other high-performing algorithms in terms of solution quality.
学科与关键词
- Two-objective robust job-shop scheduling with two problem-specific neighborhood structuresWang, Xiaozhi; Wang, Bing*; Zhang, Xianxia; Xia, Xuedong; Pan, QuankeSwarm and Evolutionary Computation, 2021, 61: 100805.被引 15
- A hybrid algorithm with a new neighborhood structure for job shop scheduling problemsXie, Jin; Li, Xinyu; Gao, Liang*; Gui, LinCOMPUTERS & INDUSTRIAL ENGINEERING, 2022, 169: 108205.被引 24
- A hybrid differential evolution and estimation of distribution algorithm based on neighbourhood search for job shop scheduling problemsZhao, Fuqing*; Shao, Zhongshi; Wang, Junbiao; Zhang, ChuckInternational Journal of Production Research, 2016, 54(4): 1039-1060.被引 45
