Optimal semi‐online algorithm for scheduling with rejection on two uniform machines

Optimal semi‐online algorithm for scheduling with rejection on two uniform machines

0.00 Avg rating0 Votes
Article ID: iaor201111134
Volume: 22
Issue: 4
Start Page Number: 674
End Page Number: 683
Publication Date: Nov 2011
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: scheduling, queues: applications
Abstract:

In this paper we consider a semi‐online scheduling problem with rejection on two uniform machines with speed 1 and s≥1, respectively. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive one by one and can be either rejected by paying a certain penalty or assigned to some machine. No preemption is allowed. The objective is to minimize the sum of the makespan of schedule, which is yielded by all accepted jobs and the total penalties of all rejected ones. Further, two rejection strategies are permitted thus an algorithm can propose two different schemes, from which the better solution is chosen. For the above version, we present an optimal semi‐online algorithm H that achieves a competitive ratio ρ H (s) as a piecewise function in terms of the speed ratio s.

Reviews

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