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

11
Last Week
0
Last month
Citations as of Aug 18, 2018

WEB OF SCIENCETM
Citations

11
Last Week
0
Last month
Citations as of Aug 14, 2018

Page view(s)

31
Last Week
0
Last month
Citations as of Aug 13, 2018

Google ScholarTM

Check

Altmetric


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