A batch-oblivious approach for complex job-shop scheduling problems

Abstract

We consider a Flexible Job-Shop scheduling problem with batching machines, reentrant flows, sequence dependent setup times and release dates while considering different regular objective functions. Semicon- ductor manufacturing is probably one of the most prominent practical applications of such a problem. Existing disjunctive graph approaches for this combined problem rely on dedicated nodes to explicitly represent batches. To facilitate modifications of the graph, our new modeling reduces this complexity by encoding batching decisions into edge weights. An important contribution is an original algorithm that takes batching decisions “on the fly”during graph traversals. This algorithm is complemented by an inte- grated move to resequence and reassign operations. This combination yields a rich neighborhood that we apply within a local search and a Simulated Annealing (SA) metaheuristic. The latter is embedded in a Greedy Randomized Adaptive Search Procedure (GRASP) which is the most efficient approach. Numerical results for benchmark instances of different problem types show the generality and applicability of our approach. The conciseness of our idea facilitates extensions towards further complex constraints needed in real-world applications.