Greedy Heuristics for Distributed Job Shop Problems

This paper studies the problem of scheduling distributed job shops where the classical single-facility job shop is extended to the multi-facility one. The problem is mathematically formulated by a mixed integer linear programming model. The small sized problems are optimally solved using commercial software of CPLEX. Three greedy heuristics, as well as adapting three well-known heuristics, are developed to solve large sized problems. The idea of the proposed heuristics is to iteratively insert operations (one at each iteration) into a sequence to build up a complete permutation of operations. The performance of the model and the six heuristics are comprehensive evaluated by numerical experiments. The results show the model and greedy heuristics are effective for the problem.