Decomposition based hybrid VNS–TS algorithm for distributed parallel factories scheduling with virtual corporation

The main purpose of this paper is to develop a decomposition based hybrid variable neighborhood search/tabu search (DVT) algorithm for multi-factory production network scheduling problem where a number of different individual factories collaborate despite their different objectives. It is assumed some of the network's factories are interested in total processing cost minimization whereas the remaining factories are interested in the production profits maximization. It is also assumed that jobs can migrate from their original factory to other factories but a transportation time is incurred. Our proposed algorithm comprises of a tabu search and a variable neighborhood search with several local search algorithms. In this hybridization, to improve the search ability of the algorithm, we make use of guiding principles with ordering of neighborhood structures by mixed integer linear programming relaxation. In the proposed algorithm, the parallel search strategy is designed for a scalar bi-objective. Multiple objectives are combined with L1-metric technique then each sub-search procedure evolves separately until a good approximation of the Pareto-front is obtained. The non-dominated sets obtained from our algorithm and original heuristic (algorithm without ordering concept) are compared using three different indices. Furthermore, the problem is modeled as a mixed integer linear programming and solved by improved ϵ-constraint approach (IEA) with CPLEX solver. The results of comparisons between IEA and DVT algorithm showed the proposed algorithm yielded most of the solutions in the net non-dominated front.