Maximizing weighted number of just-in-time jobs on unrelated parallel machines

Maximizing weighted number of just-in-time jobs on unrelated parallel machines

0.00 Avg rating0 Votes
Article ID: iaor2008727
Country: United Kingdom
Volume: 8
Issue: 5
Start Page Number: 453
End Page Number: 460
Publication Date: Oct 2005
Journal: Journal of Scheduling
Authors: ,
Abstract:

We are concerned with problems of scheduling jobs non-preemptively with the objective to maximize the weighted number of jobs that are completed exactly at their due dates. It has been shown that the problems for single machine and identical parallel machines are polynomial time solvable. The purpose of this paper is to establish the complexity status of the problem for unrelated parallel machine, which was left open. First, we present a polynomial time algorithm for solving the problem when the number of machine is fixed. Second, we show that when the number of machine is a part of input, the problem becomes NP-hard in the strong sense.

Reviews

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