A Lagrangian heuristics for balancing the average weighted completion times of two classes of jobs in a single-machine scheduling problem

We tackle a new single-machine scheduling problem, whose objective is to balance the average weighted completion times of two classes of jobs. Because both the job sets contribute to the same objective function, this problem can be interpreted as a cooperative two-agent scheduling problem, in contrapo-sition to the standard multiagent problems, which are of the competitive type since each class of job is involved only in opti-mizing its agent’s criterion. Balancing the completion times of different sets of tasks finds application in many fields, such as in logistics for balancing the delivery times, in manufacturing for balancing the assembly lines and in services for balancing the waiting times of groups of people. To solve the problem, for which we show the NP-hardness, a Lagrangian heuristic algorithm is proposed. In particular, starting from a nonsmooth variant of the quadratic assign-ment problem, our approach is based on the Lagrangian re-laxation of a linearized model and reduces to solve a finite sequence of successive linear assignment problems. Numerical results are presented on a set of randomly gen-erated test problems, showing the efficiency of the proposed technique.