Two-agent scheduling in a flowshop

Research output: Journal article publicationJournal articleAcademic researchpeer-review

22 Citations (Scopus)

Abstract

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
Volume252
Issue number2
DOIs
Publication statusPublished - 16 Jul 2016

Keywords

  • Approximation algorithm
  • Competitive agents
  • Flowshop
  • Scheduling

ASJC Scopus subject areas

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

Cite this