A branch-and-price algorithm for parallel machine scheduling with time windows and job priorities

Abstract: This paper presents a branch-and-price algorithm for scheduling n jobs on m nonhomogeneous parallel machines with multiple time windows. An additional feature of the problem is that each job falls into one of ρ priority classes and may require two operations. The objective is to maximize the weighted number of jobs scheduled, where a job in a higher priority class has “infinitely ” more weight or value than a job in a lower priority class. The methodology makes use of a greedy randomized adaptive search procedure (GRASP) to find feasible solutions during implicit enumeration and a two-cycle elimination heuristic when solving the pricing subproblems. Extensive computational results are presented based on data from an application involving the use of communications relay satellites. Many 100-job instances that were believed to be beyond the capability of exact methods