Please use this identifier to cite or link to this item:
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
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.
ISSN: 0305-0483
EISSN: 1873-5274
DOI: 10.1016/
Appears in Collections:Journal/Magazine Article

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


Last Week
Last month
Citations as of Aug 20, 2017

Page view(s)

Last Week
Last month
Checked on Aug 20, 2017

Google ScholarTM



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