Paper Info
Title
A New Concept in Advice Complexity of Job Shop Scheduling.
Abstract
In online scheduling problems, we want to assign jobs to machines while optimizing some given objective function. In the class we study in this paper, we are given a number m of machines and two jobs that both want to use each of the given machines exactly once in some predefined order. Each job consists of m tasks and each task needs to be processed on one particular machine. The objective is to assign the tasks to the machines while minimizing the makespan, i.e., the processing time of the job that takes longer. In our model, the tasks arrive in consecutive time steps and an algorithm must assign a task to a machine without having full knowledge of the order in which the remaining tasks arrive. We study the advice complexity of this problem, which is a tool to measure the amount of information necessary to achieve a certain output quality. A great deal of research has been carried out in this field; however, this paper studies the problem in a new setting. In this setting, the oracle does not know the exact future anymore but only all possible future scenarios and their probabilities. This way, the additional information becomes more realistic. We prove that the problem is more difficult with this oracle than before. Moreover, in job shop scheduling, we provide a lower bound of 1+1/(6 root m) on the competitive ratio of any online algorithm with advice and prove an upper bound of 1+1/root m on the competitive ratio of an algorithm from Hromkovic et al. [8].
Year
DOI
Venue
2014
10.1007/978-3-319-14896-0_13
Lecture Notes in Computer Science
Field
DocType
Volume
Online algorithm,Job shop scheduling,Upper and lower bounds,Computer science,Scheduling (computing),Oracle,Theoretical computer science,Competitive analysis
Conference
8934
ISSN
Citations 
PageRank 
0302-9743
1
0.35
References 
Authors
6
1
Name
Order
Citations
PageRank
David Wehner121.03