Two-agent scheduling in a flowshop

Research output: Journal article publicationJournal articleAcademic researchpeer-review

33 Citations (Scopus)


In this paper we study two-agent scheduling in a two-machine flowshop. The cost function is the weighted sum of some common regular functions, including the makespan and the total completion time. Specifically, we consider two problems, namely the problem to minimize the weighted sum of both agents' makespan, and the problem to minimize the weighted sum of one agent's total completion time and the other agent's makespan. For the first problem, we give an ordinary NP-hardness proof and a pseudo-polynomial-time algorithm. We also analyze the performance of treating the problem using Johnson's rule and propose an approximation algorithm based on Johnson's rule. For the second problem, we propose an approximation algorithm based on linear programming relaxation of the problem. Finally, we show that some simple algorithms can be used to solve special cases of the two problems.
Original languageEnglish
Pages (from-to)376-384
Number of pages9
JournalEuropean Journal of Operational Research
Issue number2
Publication statusPublished - 16 Jul 2016


  • Approximation algorithm
  • Competitive agents
  • Flowshop
  • Scheduling

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'Two-agent scheduling in a flowshop'. Together they form a unique fingerprint.

Cite this