Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/66733
Title: Two-agent scheduling in a flowshop
Authors: Fan, BQ
Cheng, TCE 
Keywords: Scheduling
Competitive agents
Flowshop
Approximation algorithm
Issue Date: 2016
Publisher: Elsevier
Source: European journal of operational research, 16 Jul. 2016, v. 252, no. 2, p. 376-384 How to cite?
Journal: European journal of operational research 
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.
URI: http://hdl.handle.net/10397/66733
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/j.ejor.2016.01.009
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

6
Citations as of Dec 4, 2017

WEB OF SCIENCETM
Citations

5
Last Week
0
Last month
Citations as of Dec 9, 2017

Page view(s)

18
Last Week
2
Last month
Checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.