ISSN:
1436-4646
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We consider the formulation of non-preemptive single machine scheduling problems using time-indexed variables. This approach leads to very large models, but gives better lower bounds than other mixed integer programming formulations. We derive a variety of valid inequalities, and show the role of constraint aggregation and the knapsack problem with generalised upper bound constraints as a way of generating such inequalities. A cutting plane/branch-and-bound algorithm based on these inequalities has been implemented. Computational experience on small problems with 20/30 jobs and various constraints and objective functions is presented.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01586059
