Paper Info
Title
Online And Semi-Online Scheduling To Minimize Makespan On Single Machine With An Availability Constraint
Abstract
Online and semi-online scheduling problems on a single machine with an availability constraint are considered in this paper. The machine has one unavailable interval in which jobs cannot be processed. Preemption is not allowed. Jobs arrive over time. The objective is to minimize makespan. First we discuss the online version of the problem. After giving its lower bound, we prove that Earliest Release Date (ERD) algorithm is an optimal algorithm. Then we study some semi-online problems in which the largest processing time, the total processing time, the largest release date, or the optimal makespan is known in advance. For these semi-online problems, we give their lower bounds, design semi-online algorithms and prove their competitive ratios, respectively.
Year
DOI
Venue
2015
10.1142/S1793830915500214
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS
Keywords
Field
DocType
Scheduling, online, semi-online, availability constraint, algorithm
Discrete mathematics,Mathematical optimization,Preemption,Job shop scheduling,Release date,Scheduling (computing),Upper and lower bounds,Computer science,Johnson's rule,Distributed computing
Journal
Volume
Issue
ISSN
7
3
1793-8309
Citations 
PageRank 
References 
0
0.34
9
Authors
3
Name
Order
Citations
PageRank
Qiang Gao125451.34
Ganggang Li200.68
Xiwen Lu318221.03