Full Screen Search.pdf

Title Page Problem Definition Related works Our results 1 / 20 JJ II J I ←? ?→ Full Screen Search Close by Yiwei Jiang 19 Dec. 2005 The 16th Annual International Symposium on Algorithms and Computation December 19 - 21, 2005, Sanya, Hainan, China Preemptive semi-online scheduling with inexact partial information Yong He Yiwei Jiang Department of Mathematics, Zhejiang University, Hangzhou 310027, P. R. China mathjyw@ Title Page Problem Definition Related works Our results 2 / 20 JJ II J I ←? ?→ Full Screen Search Close by Yiwei Jiang 19 Dec. 2005 Outline 1 Problem Definition 3 Preemptive scheduling P(Q)|pmpt|Cmax . . . . 3 Inexact partial information . . . . . . . . . . . 6 Algorithm measure . . . . . . . . . . . . . . . 7 2 Related works 8 3 Our results 10 Optimal algorithm for Pm|pmpt,dis opt|Cmax . 12 Optimal algorithm for Q2|pmpt,dis opt|Cmax . . 14 Optimal algorithm for Q2|pmpt,dis opt|Cmax . . 17 Title Page Problem Definition Related works Our results 3 / 20 JJ II J I ←? ?→ Full Screen Search Close by Yiwei Jiang 19 Dec. 2005 1 Problem Definition Preemptive scheduling P(Q)|pmpt|Cmax ? A job set J = {p1, p2, . . . , pn} A machine set M = {M1,M2, . . . ,Mm}. ? Two classes of machines: Identical machine P: Mi has a speed of 1. Uniform machine Q: Mi has a speed of si ≥ 1. p j ?→Mi, p j/si time units. (Q2 : 1 = s1 ≤ s2 = s.) ? Preemption(pmpt) : It is allowed to split a job and spread its processing over different machines in non- overlapping time slots. ? The objective is to minimize the maximum machine completion time Cmax (makespan). Title Page Problem Definition Related works Our results 4 / 20 JJ II J I ←? ?→ Full Screen Search Close by Yiwei Jiang 19 Dec. 2005 Three scheduling versions ? Offline Have full information on the job data before constructing a schedule. ? Online Jobs arrive one by one over list and are required to be scheduled irrevocably onto the machines as soon as they are given, without any knowledge about jobs that follow later on. ? semi-onlin