Flexible job-shop scheduling with flexible workdays, preemption, overlapping in operations and satisfaction criteria: an industrial application

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 (N0?N1?N2?N3?N4) 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 N4-based GGTS demonstrates performance competitive with that of the EGA and the GGTSs based on the other neighbourhood functions (N0, N1, N2 and N3) for solving the scheduling problem.