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

Yunqiang Yin, Wenyi Wang, Dujuan Wang, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

16 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)202-215
Number of pages14
JournalComputers and Industrial Engineering
Publication statusPublished - 1 Sep 2017


  • DIF due date assignment
  • Dynamic programming
  • Multiple agents
  • Scheduling

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this