Algorithms for Fair Repetitive Scheduling

We consider a single machine scheduling problem consisting of $\boldsymbol{n}$ clients and q consecutive operational periods (e.g., days). Each client submits a single job to processing on each of the days and wants his jobs to be completed as early as possible. A solution is defined by a set of q schedules (one per day), and it is classified as a K-fair solution if the total completion time of any of the clients on the entire set of q days is not greater than K. The scheduler’s objective is to obtain a K-fair solution with the minimum possible K value. The problem is known to be strongly NPhard, but no practical techniques were developed for solving it. Our main goal is to close this gap in the literature by providing a set of tools to maximize the system’s fairness. To do so, we design a mixed integer linear programming formulation, two greedy algorithms and a metaheuristic. We intend to compute the entire set of algorithms and to test the quality of the different algorithms by applying an extensive experimental study.