Article ID: | iaor201524007 |
Volume: | 61 |
Issue: | 1 |
Start Page Number: | 1 |
End Page Number: | 16 |
Publication Date: | Feb 2014 |
Journal: | Naval Research Logistics (NRL) |
Authors: | Mosheiov Gur, Gerstl Enrique |
Keywords: | production, production: JIT, combinatorial optimization, programming: dynamic |
In scheduling problems with two competing agents, each one of the agents has his own set of jobs to be processed and his own objective function, and both share a common processor. In the single‐machine problem studied in this article, the goal is to find a joint schedule that minimizes the total deviation of the job completion times of the first agent from a common due‐date, subject to an upper bound on the maximum deviation of job completion times of the second agent. The problem is shown to be NP‐hard even for a nonrestrictive due‐date, and a pseudopolynomial dynamic program is introduced and tested numerically. For the case of a restrictive due‐date (a sufficiently small due‐date that may restrict the number of early jobs), a faster pseudopolynomial dynamic program is presented. We also study the multiagent case, which is proved to be strongly NP‐hard. A simple heuristic for this case is introduced, which is tested numerically against a lower bound, obtained by extending the dynamic programming algorithm.