Computer and Job-shop Scheduling TheoryIntroduction to deterministic scheduling theory; Algorithms for minimal-length schedulesComplexity of sequencing problems; Enumerative and iterative computationsl approaches. |
Common terms and phrases
3-satisfiability a₁ approximate algorithms arbitrary AS/DB assigned assume b₁ b₂ BB₁ BB₂ BFST BFST₁ bound branch-and-bound algorithm branching node branching step Chapter complete solution computational requirements construct D₁ defined denote dynamic programming elements elimination rules example feasible FIFO Figure finishing flow pattern flow-shop problem given graph heuristic input integer job-shop problem job-system knapsack problem labeling Lemma length list schedule lower-bound function mean weighted flow minimal mwft neighborhood nonpreemptive schedule NP-complete number of processors optimal permutation optimal schedule optimal solution p-maximal set P₁ parameters partial solutions polynomial polynomial-time precedence constraint preemptive schedule Proof random variable resource S₁ scheduling problem scheduling rule scheduling theory secondary storage sequence set with respect subset T₁ T₂ task system tasks executed Theorem traveling salesman problem tree U/DBAS U₁ upper-bound solution variables X₁ Y₁ π₂