High Performance Algorithms for the Unrelated Parallel Machines Scheduling Problem with a Common Server and Job-Sequence Dependent Setup Times
摘要
In this paper we study a variant of the non-preemptive unrelated parallel machines scheduling problem with sequence-dependent setup times and machine eligibility restrictions. We first formulate the problem as a mixed integer linear program (MILP), and further devise a branch-and-cut (B&C) algorithm for solving the problem. Due to the NP hardness of the problem, we propose a metaheuristic based on an iterated local search (ILS) algorithm. Using this, we provide several matheuristics for solving the problem. The proposed approaches are compared using different families of instances.