Two-agent singe-machine scheduling with release times to minimize the total weighted completion time

Edwin Tai Chiu Cheng, Yu Hsiang Chung, Shan Ci Liao, Wen Chiung Lee

Research output: Journal article publicationJournal articleAcademic researchpeer-review

38 Citations (Scopus)


In many management situations multiple agents pursuing different objectives compete on the usage of common processing resources. In this paper we study a two-agent single-machine scheduling problem with release times where the objective is to minimize the total weighted completion time of the jobs of one agent with the constraint that the maximum lateness of the jobs of the other agent does not exceed a given limit. We propose a branch-and-bound algorithm to solve the problem, and a primary and a secondary simulated annealing algorithm to find near-optimal solutions. We conduct computational experiments to test the effectiveness of the algorithms. The computational results show that the branch-and-bound algorithm can solve most of the problem instances with up to 24 jobs in a reasonable amount of time and the primary simulated annealing algorithm performs well with an average percentage error of less than 0.5% for all the tested cases.
Original languageEnglish
Pages (from-to)353-361
Number of pages9
JournalComputers and Operations Research
Issue number1
Publication statusPublished - 1 Jan 2013


  • Maximum lateness
  • Scheduling
  • Total weighted completion time
  • Two agents

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this