 Two-agent scheduling in a flowshopB.Q. Fan and T.C.E. Cheng European Journal of Operational Research, 2016, vol. 252, issue 2, 376-384 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. Keywords: Scheduling; Competitive agents; Flowshop; Approximation algorithm (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:252:y:2016:i:2:p:376-384 DOI: 10.1016/j.ejor.2016.01.009 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.