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

<p>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 (<i>N</i>0 ⊇ <i>N</i>1 ⊇ <i>N</i>2 ⊇ <i>N</i>3 ⊇ <i>N</i>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 <i>N</i>4-based GGTS demonstrates performance competitive with that of the EGA and the GGTSs based on the other neighbourhood functions (<i>N</i>0, <i>N</i>1, <i>N</i>2 and <i>N</i>3) for solving the scheduling problem.