Balancing the average weighted completion times of two classes of jobs: a new scheduling problem

Abstract

Exploring a new area of the scheduling theory and inspired by a real application in an academic context, in this thesis we introduce a new single-machine two-agent scheduling problem, aimed at balancing the average weighted completion times of two different classes of jobs, one per agent. Differently from the common multiagent cases, which are generally of the competing type, this problem could be interpreted as a cooperative type problem. In fact, even if the two agents share the same machine, they cooperate to optimize the unique global objective function, in order to balance their average weighted completion times. While for the case with identical jobs and unitary weight we present an exact algorithm providing an optimal solution in linear time, for the general case we prove the NP-hardness of the problem and we propose a mathematical formulation as a variant of the well known quadratic assignment problem. By applying the Glover linearization, we obtain a mixed integer linear program exploited to design a Lagrangian heuristics based on solving, at each iteration, a linear assignment problem. Since the proposed algorithm has revealed to be able to solve instances up to 500 jobs, in order to face larger scale instances (up to 2000 jobs) we also propose a genetic algorithm.