Multi-agent single-machine scheduling and unrestricted due date assignment with a fixed machine unavailability interval

- We study due date assignment and scheduling with multiple agents.
- The machine has a fixed unavailability interval.
- Three problems with different optimization criteria are investigated.
- Computational complexity status and efficient solution algorithms are provided.
- Numerical studies are conducted to assess the performance of the proposed algorithms.

We consider the problem of scheduling n nonresumable and simultaneously available jobs on a single machine with several agents. Each job belongs to one of the agents, each of which competes for the use of the machine to process its own jobs to meet its own scheduling criterion. The machine has a fixed interval during which it is unavailable to process the jobs. The due dates of the last agent's jobs are decision variables, which are determined by the unrestricted (different) due date assignment model, while the due dates of each of the other agents' jobs are given in advance. The last agent wishes to minimize the sum of the due date assignment cost and weighted number of its tardy jobs, while each of the other agents seeks to minimize the maximum value of a regular scheduling function of its jobs, the total completion time of its jobs, or the weighted number of its tardy jobs. The overall objective is to minimize the last agent's criterion, while keeping each of the other agents' criterion values no greater than a given limit. We analyze the computational complexity, and devise pseudo-polynomial dynamic programming (DP) solution algorithms and mixed integer linear programming (MILP) formulations for the considered problems. Finally, we compare the performance of the DP solution algorithms against the corresponding MILP formulations with randomly generated instances.