Modeling and heuristics for scheduling of distributed job shops

• This paper deals with the problem of distributed job shop scheduling.
• Two mixed integer linear programming models (sequence- and position-based) are proposed.
• Besides adapting three well-known heuristics, three greedy heuristics are developed.
• Three theorems are defined to analyze redundancy of permutation scheme and used to improve heuristics.
• Comprehensive experiments are conducted to evaluate the performance of the two models and the six developed heuristics.

This paper deals with the problem of distributed job shop scheduling in which the classical single-facility job shop is extended to the multi-facility one. The mathematical formulation of the problem is comprehensively discussed. Two different mixed integer linear programming models in form of sequence and position based variables are proposed. Using commercial software of CPLEX, the small sized problems are optimally solved. To solve large sized problems, besides adapting three well-known heuristics, three greedy heuristics are developed. The basic idea behind the developed heuristics is to iteratively insert operations (one at each iteration) into a sequence to build up a complete permutation of operations. The permutation scheme, although having several advantages, suffers from redundancy which is having many different permutations representing the same schedule. The issue is analyzed to recognize the redundant permutation. That improves efficiency of heuristics. Comprehensive experiments are conducted to evaluate the performance of the two models and the six heuristics. The results show sequence based model and greedy heuristics equipped with redundancy exclusion are effective for the problem.