Two-agent single-machine scheduling with release dates and preemption to minimize the maximum lateness

Research output: Journal article publicationJournal articleAcademic researchpeer-review

10 Citations (Scopus)

Abstract

We consider two-agent scheduling on a single machine with release dates and preemption to minimize the maximum lateness. In this scheduling model, there are two agents (Formula presented.) each having his own job set (Formula presented.), respectively. Each job (Formula presented.) has a release date (Formula presented.) jobs need to be preemptively scheduled on a single machine. Leung et al. (Oper Res 58:458–469, 2010) present a comprehensive study of two-agent scheduling in various machine environments. They show that problem (Formula presented.) can be solved in (Formula presented.) time. They use the strategy that schedules the jobs of agent (Formula presented.) without preemption as late as possible under the restriction (Formula presented.). We show that the strategy fails to work even when (Formula presented.), invalidating their result. We then study the minimization problem (Formula presented.) and the Pareto optimization problem (Formula presented.). We show that the two problems can be solved in (Formula presented.) time, respectively.
Original languageEnglish
Pages (from-to)147-153
Number of pages7
JournalJournal of Scheduling
Volume18
Issue number2
DOIs
Publication statusPublished - 1 Jan 2015

Keywords

  • Pareto optimization
  • Single machine
  • Two-agent scheduling

ASJC Scopus subject areas

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

Cite this