Scheduling with machine cost and rejection

Scheduling with machine cost and rejection

0.00 Avg rating0 Votes
Article ID: iaor20071759
Country: Netherlands
Volume: 12
Issue: 4
Start Page Number: 337
End Page Number: 350
Publication Date: Dec 2006
Journal: Journal of Combinatorial Optimization
Authors: ,
Abstract:

In this paper we consider the scheduling problem with machine cost and rejection penalties. For this problem, we are given a sequence of independent jobs, each being characterized by its processing time (size) and its penalty. No machine is initially provided, and when a job is revealed the algorithm has the option to purchase new machines. Right when a new job arrives, we have the following choices: (i) reject it, in which case we pay its penalty; (ii) non-preemptively process it on an existing machine, which contributes to the machine load; (iii) purchase a new machine, and assign it to this machine. The objective is to minimize the sum of the makespan, the cost for purchasing machines, and the total penalty of all rejected jobs. For the small job case (where all jobs have sizes no greater than the cost for purchasing one machine, and which is the generalization of the Ski-Rental Problem) we present an optimal online algorithm with a competitive ratio of 2.

Reviews

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