Scheduling with two competing agents to minimize total weighted earliness

Scheduling with two competing agents to minimize total weighted earliness

0.00 Avg rating0 Votes
Article ID: iaor20171863
Volume: 253
Issue: 1
Start Page Number: 227
End Page Number: 245
Publication Date: Jun 2017
Journal: Annals of Operations Research
Authors: , ,
Keywords: scheduling, manufacturing industries, combinatorial optimization, game theory, programming: dynamic, heuristics
Abstract:

We study a single machine scheduling problem with two competing agents and earliness measures. Given a common deadline for all the jobs of both agents, the objective function is minimizing the total weighted earliness of the first agent, subject to an upper bound on the maximum earliness of the jobs of the second agent. This problem was recently proved to be NP‐hard, leaving the question of the complexity class open. We introduce a pseudo‐polynomial dynamic programming algorithm, implying that the problem is NP‐hard in the ordinary sense. An extensive numerical study indicates that the dynamic programming is very effective for solving medium size instances. We also propose an efficient heuristic, which is shown numerically to produce very close‐to‐optimal schedules. The dynamic programming algorithm is extended to any (given) number of agents, proving NP‐hardness in the ordinary sense of the general multi‐agent setting. Finally, we study the inverse problem of minimizing the maximum earliness of one agent subject to an upper bound on the maximum total weighted earliness of the second agent. We introduce a pseudo‐polynomial dynamic programming algorithm, a simple greedy‐type heuristic and a lower bound. Our numerical tests verify that the heuristic produces very small optimality gaps.

Reviews

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