A common framework and taxonomy for multicriteria scheduling problems with Interfering and competing Jobs: Multi-agent scheduling problems

摘要

Most classical scheduling research assumes that the objectives sought are common to all jobs to bescheduled. However, many real-life applications can be modeled by considering different sets of jobs,each one with its own objective(s), and an increasing number of papers addressing these problems hasappeared over the last few years. Since so far the area lacks a uni ed view, the studied problemshave received different names (such as interfering jobs, multi-agent scheduling, mixed-criteria, etc), someauthors do not seem to be aware of important contributions in related problems, and solution proceduresare often developed without taking into account existing ones. Therefore, the topic is in need of a commonframework that allows for a systematic recollection of existing contributions, as well as a clear de nitionof the main research avenues. In this paper we review multicriteria scheduling problems involving two ormore sets of jobs and propose an uni ed framework providing a common de nition, name and notationfor these problems. Moreover, we systematically review and classify the existing contributions in termsof the complexity of the problems and the proposed solution procedures, discuss the main advances, andpoint out future research lines in the topic.