Two-agent single-machine scheduling with release times and deadlines

Yunqiang Yin, Shuenn Ren Cheng, Edwin Tai Chiu Cheng, Wen Hung Wu, Chin Chia Wu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

39 Citations (Scopus)


Multiple-agent scheduling has attracted considerable research attention in recent years. However, studies of multiple-agent scheduling with release times and deadlines are few. In the presence of ready times, sometimes it is beneficial to wait for future job arrivals in constructing a schedule. Inspired by the importance of ready times, we study the single-machine two-agent scheduling problem with releases times and deadlines to minimise the number of tardy jobs of one agent under the restriction that the maximum lateness of the jobs of the other agent cannot exceed a given value Q. Having established that the problem is strongly NP-hard, we provide a branch-and-bound and a simulated annealing algorithm to search for the optimal and approximate solutions, respectively. The results of computational experiments reveal that the SA algorithm can generate near-optimal solutions quickly.
Original languageEnglish
Pages (from-to)75-94
Number of pages20
JournalInternational Journal of Shipping and Transport Logistics
Issue number1
Publication statusPublished - 1 Jan 2013


  • Release times
  • Scheduling
  • Simulated annealing
  • Two agents

ASJC Scopus subject areas

  • Business and International Management
  • Transportation
  • Management Science and Operations Research
  • Management of Technology and Innovation


Dive into the research topics of 'Two-agent single-machine scheduling with release times and deadlines'. Together they form a unique fingerprint.

Cite this