Single machine just-in-time scheduling problems with two competing agents

Single machine just-in-time scheduling problems with two competing agents

0.00 Avg rating0 Votes
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: ,
Keywords: production, production: JIT, combinatorial optimization, programming: dynamic
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.