Flexible job-shop scheduling with flexible workdays, preemption, overlapping in operations and satisfaction criteria: an industrial application. Issue 16 (17th August 2016) - Zhang, Jiae; Yang, Jianjun
Abstract : This paper addresses a real scheduling problem, namely, a complex flexible job-shop scheduling problem (FJSP) with special characteristics (flexible workdays, preemption and overlapping in operations), where the objective is to maximise a satisfaction criterion defined through goal programming. To allow for flexible workdays, the solution representation of the classical FJSP is extended to consider overtime decisions and a sequence of time-cell states, which is used to model resource capability. A new temporal-constraint-handling method is proposed to solve the problem of overlapping in operations in a flexible-workday environment. Three solution methods are proposed to solve this scheduling problem: a heuristic method based on priority rules, a goal-guided tabu search (GGTS) and an extended genetic algorithm (EGA). In the GGTS, the neighbourhood functions are defined based on elimination approaches, and five possible neighbourhood functions ( N 0 ⊇  N 1 ⊇  N 2 ⊇  N 3 ⊇  N 4) are presented. The effectiveness and efficiency of the three solution methods are verified using dedicated benchmark instances. Computational simulations and comparisons indicate that the proposed N 4-based GGTS demonstrates performance competitive with that of the EGA and the GGTSs based on the other neighbourhood functions ( N 0, N 1, N 2 and N 3) for solving the scheduling problem.