Distributed parallel machines scheduling in the heterogeneous production network: a variable neighborhood search

摘要

Distributed parallel machines scheduling problems (DPMSP) are not investigated fully. In this study DPMSP is studied in the heterogeneous production network, the goal of which is to minimize makespan. An effective variable neighborhood search (VNS) is proposed, in which the coupled relations among sub-problems are used. Only factory assignment is optimized by VNS and other sub-problems are solved by heuristic. A new way is used to compute the initial number of jobs in each factory and a simple coding method is applied to describe factory assignment. Two effective neighborhood structures are presented to generate new solutions of factory assignment. Extensive experiments are conducted to test the performance of VNS and computational results show that VNS is an effective and efficient method for DPMSP.