15 pages matching bound is tight in this book
Results 1-3 of 15
What people are saying - Write a review
We haven't found any reviews in the usual places.
Algorithm 5.2 algorithm CLS algorithm LBT analysis approximation algorithm assigned to machine batch j1 batch setup bound is tight Chapter Chen Cmax(S complete batch contradiction Corollary critical jobs deﬁned denote dense schedule dule example facility F ﬁnd ﬁnishing ﬁrst job found by Algorithm greedy algorithm Hence heuristic schedule holds identical parallel machines idle interval implies inequality job set jobs of batch jobs on machine Johnson’s algorithm Lemma lower bound LPT rule LPT schedules machine loads machine M1 non-preemptive number of jobs O(n log on-line algorithm operation optimal makespan optimal permutation optimal schedule optimum permutation 1r1 permutation schedule polynomial polynomial-time approximation scheme preemption preemptive scheduling problem F problem instances processes jobs Proof prove respectively satisﬁed sche schedule with makespan scheduling theory sequence speciﬁed stage strongly NP-complete strongly NP-hard subsection Suppose taak Theorem thesis two-machine ﬂow type 1 batch workload worst-case performance ratio worst-case ratio