Two-agent scheduling on unrelated parallel machines with total completion time and weighted number of tardy jobs criteria

This paper considers a two-agent scheduling problem in which each agent has a set of jobs that competes with that of another agent for the use of m unrelated parallel machines. Each agent aims to minimize a certain scheduling criterion related to the completion times of its jobs. The overall objective is to minimize the total completion time of the jobs of one agent while keeping the weighted number of tardy jobs of another agent within a given limit. We introduce a novel column generation scheme, called in-out column generation, to maintain the stability of dual variables and then embed this scheme into a branch-and-price framework. A greedy heuristic is used to obtain a set of initial columns to start the in-out column generation. The pricing subproblem in the column generation scheme is formulated as a single-machine scheduling problem that can be solved using dynamic programming techniques. An efficient branching strategy that is compatible with pricing subproblems is also proposed. The extensive computational results that are obtained by using randomly generated data demonstrate that our branch-and-price algorithm is singularly efficient and promising.