A branch-and-price algorithm for identical parallel machine scheduling with multiple milestones

This article considers an identical parallel-machine task scheduling problem motivated by operations management of online services. A task with an integer processing time can be split into sub-tasks with integer processing times. Each task has multiple integer milestones and at each milestone a nonnegative penalty will occur. The penalty value of a task at a milestone is a convex nonincreasing function of the completed amount by this milestone. Our objective is to determine a feasible schedule for all the tasks on given identical parallel machines, such that the sum of all tasks' total penalty at all milestones is minimized. We prove the NP-hardness of this problem in the ordinary sense and develop a branch-and-price algorithm. Computational experiments utilizing data from an online service operations survey show that this algorithm is singularly efficient and promising.