Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/66701
Title: Just-in-time scheduling with two competing agents on unrelated parallel machines
Authors: Yin, YQ
Cheng, SR
Cheng, TCE 
Wang, DJ
Wu, CC
Keywords: Scheduling
Two agents
Unrelated parallel machines
Just-in-time scheduling
FPTAS
Issue Date: 2016
Publisher: Pergamon Press
Source: Omega, Sept. 2016, v. 63, p. 41-47 How to cite?
Journal: Omega 
Abstract: This paper considers two-agent just-in-time scheduling where agents A and B have to share m unrelated parallel machines for processing their jobs. The objective of agent A is to maximize the weighted number of its just-in-time jobs that are completed exactly on their due dates, while the objective of agent B is either to maximize its maximum gain (income) from its just-in-time jobs or to maximize the weighted number of its just-in-time jobs. We provide a bicriterion analysis of the problem, which seek to find the Pareto-optimal solutions for each combination of the two agents' criteria. When the number of machines is part of the problem instance, both the addressed problems are NP-hard in the strong sense. When the number of machines is fixed, we show that the problem of maximizing agent A's weighted number of just-in-time jobs while maximizing agent B's maximum gain can be solved in polynomial time, whereas the problem of maximizing both agents' weighted numbers of just-in-time jobs is NP-hard. For the latter problem, we also provide a pseudo-polynomial-time solution algorithm, establishing that it is NP-hard in the ordinary sense, and show that it admits a fully polynomial-time approximation scheme (FPTAS) for finding an approximate Pareto solution.
URI: http://hdl.handle.net/10397/66701
ISSN: 0305-0483
EISSN: 1873-5274
DOI: 10.1016/j.omega.2015.09.010
Appears in Collections:Journal/Magazine Article

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

WEB OF SCIENCETM
Citations

6
Last Week
0
Last month
Citations as of Aug 20, 2017

Page view(s)

14
Last Week
3
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



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