Job shop scheduling with a non-regular objective: A comparison of neighbourhood structures based on a sequencing/timing decomposition

Commercial software packages for production management are characterized by a gap between MRP logic, based on a backward scheduling approach, and finite capacity scheduling, usually based on forward scheduling. In order to partially bridge that gap, we need scheduling algorithms able to meet due dates while keeping WIP and inventory costs low. This leads us to consider job shop scheduling problems characterized by non-regular objective functions; such problems are even more difficult than classical job shop scheduling, and suitable heuristics are needed. One possibility is to consider local search strategies based on the decomposition of the overall problem into sequencing and timing sub-problems. For given job sequences, the optimal timing problem can be solved as a node potential problem on a graph. Since solving the timing problem is a relatively time-consuming task, we need to define a suitable neighbourhood structure to explore the space of job sequences; this can be done by generalizing well-known results for the minimum makespan problem. A related issue is if solving timing problems exactly is really necessary, or if an approximate solution is sufficient; hence, we also consider solving the timing problem approximately by a fast heuristic. We compare different neighbourhood structures, by embedding them within a pure local improvement strategy. Computational experiments show that the overall approach performs better than release/dispatch rules, although the performance improvement depends on the problem characteristics, and that the fast heuristic is quite competitive with the optimal timing approach. On the one hand, these results pave the way to the development of better local search algorithms (based e.g. on tabu search); on the other hand, it is worth noting that the heuristic timing approach, unlike the optimal one, can be extended to cope with the complicating features typical of practical scheduling problems.