Scheduling Theory Single-Stage Systems

Preface. Introduction. <strong>1: Elements of Graph Theory and Computational</strong> <strong>Complexity of Algorithms. 1.</strong> Sets, Orders, Graphs. <strong>2.</strong> Balanced 2-3-Trees. <strong>3.</strong> Polynomial Reducibility of Discrete Problems. Complexity of Algorithms. <strong>4.</strong> Bibliography and Review. <strong>2:</strong> <strong>Polynomially Solvable Problems. 1.</strong> Preemption. <strong>2.</strong> Deadline-Feasible Schedules. <strong>3.</strong> Single Machine. Maximal Cost. <strong>4.</strong> Single Machine. Total Cost. <strong>5.</strong> Identical Machines. Maximal Completion Time. Equal Processing Times. <strong>6.</strong> Identical Machines. Maximal Completion Time. Preemption. <strong>7.</strong> Identical Machines. Due Dates. Equal Processing Times. <strong>8.</strong> Identical Machines. Maximal Lateness. <strong>9.</strong> Uniform and Unrelated Parallel Machines. Total and Maximal Cost. <strong>10.</strong> Bibliography and Review. <strong>3: Priority-Generating Functions. Ordered Sets of Jobs. 1.</strong> Priority-Generating Functions. <strong>2.</strong> Elimination Conditions. <strong>3.</strong> Tree-like Order. <strong>4.</strong> Series-Parallel Order. <strong>5.</strong> General Case. <strong>6.</strong> Convergence Conditions. <strong>7.</strong> 1-Priority-Generating Functions. <strong>8.</strong> Bibliography and Review. <strong>4: NP-Hard Problems. 1.</strong> Reducibility of the Partition Problem. <strong>2.</strong> Reducibility of the 3-Partition Problem. <strong>3.</strong> Reducibility of the Vertex Covering Problem. <strong>4.</strong> Reducibility of the Clique Problem. <strong>5.</strong> Reducibility of the Linear Arrangement Problem. <strong>6.</strong> Bibliographic Notes. <strong>Appendix.</strong> Approximation Algorithms. References. Additional References. Index. <br/>