## Machine scheduling problems: classification, complexity and computations |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

INTRODUCTION | 1 |

METHODS OF SOLUTION | 30 |

ONEMACHINE PROBLEMS | 56 |

Copyright | |

8 other sections not shown

### Other editions - View all

### Common terms and phrases

active schedules acyclic directed graph approach assignment problem assumptions branching rule calculated chapter Cmax completion complexity results corresponding criterion ct(t DIRECTED HAMILTONIAN DIRECTED HAMILTONIAN CIRCUIT discussed in section disjunctive arcs disjunctive graph due dates dynamic programming efficient algorithm elimination criteria encoding equivalent feasible flow-shop given HAMILTONIAN PATH Hence heuristic implicit enumeration implies indicate integer job-shop job-shop problem jobs Jj KNAPSACK OC Lawler LB(u LB(W LB(Z LBk(D lower bound machine scheduling problems McMahon minimize non-bottleneck machine non-decreasing notation NP-complete obtained operations optimal schedule ordering the jobs OreMk partial schedule permutation polynomial-bounded possible precedence constraints precedence graph precedes Jj prior distribution priority rules problem is NP-complete procedure processing order proof regular measures respect restrict SARA Computing scheduling theory search tree sequence independent solve steps subset Table tardiness theorem theorem 4.6 travelling salesman problem unary vertex