scientific article; zbMATH DE number 3850790
combinatorial optimizationcomputational experimentsdeterministic sequencingheuristicpolynomial-time algorithmsprecedence constraintssingle machine
Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01) Deterministic scheduling theory in operations research (90B35) Integer programming (90C10) Dynamic programming (90C39)
This monograph is devoted to one of the central problems in deterministic sequencing theory: a number of jobs with given processing times, weights, and precedence constraints, have to be scheduled on a single machine such that the total weighted completion time is minimized. The author first reviews the previous work on this problem: polynomial- time algorithms for certain special cases, NP-hardness results for other (more general) special cases, fast approximation algorithms (mostly priority rules followed by local improvements), and enumerative optimization methods (dynamic programming and branch-and-bound). Next, he proposes a new integer programming formulation of the problem. For the associated linear program, a specialized version of the simplex method is given that exploits the structure of the coefficient matrix. A heuristic is developed which can be viewed as a modification of subgradient optimization; the approach seems to be applicable to other problems in combinatorial optimization. A report on computational experiments concludes this useful and well-written monograph. The reader who is confused by the bilingual title of this book should know that it is written in German and has an informative thirteen-page abstract in English.
- Mean flow time minimization with given bounds of processing times
- scientific article; zbMATH DE number 4152130
- Flowshop sequencing with mean flowtime objective
- A greedy heuristic for the mean tardiness sequencing problem
- Hybrid optimization methods for time-dependent sequencing problems
- Solution of the Liu-Layland problem via bottleneck just-in-time sequencing
- Special class of flowshop sequencing problems
- Reoptimization of the minimum total flow-time scheduling problem
- A survey of results for sequencing problems with controllable processing times
- Minimizing mean flow time with parallel processors and resource constraints
- A sequencing problem in the weaving industry
- Sequencing with restrictions in processing times
- The weighted fair sequences problem
- A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments
- Minimizing flowtime and missed due-dates in single-machine sequencing
- A survey on the linear ordering problem for weighted or unweighted tournaments
- An iterative exact algorithm for the weighted fair sequences problem
- scientific article; zbMATH DE number 3843480 (Why is no real title available?)
- scientific article; zbMATH DE number 4170624 (Why is no real title available?)
- scientific article; zbMATH DE number 4170625 (Why is no real title available?)
- Semidefinite relaxations of ordering problems
- A Sequencing Problem with Release Dates and Clustered Jobs
- Optimal Sequencing Via Modular Decomposition: Characterization of Sequencing Functions
- scientific article; zbMATH DE number 4020828 (Why is no real title available?)
- scientific article; zbMATH DE number 4076943 (Why is no real title available?)
- A branch and bound algorithm for minimizing weighted completion times with deadlines
- On preference orders for sequencing problems or, what hath Smith wrought?
- A benchmark library and a comparison of heuristic methods for the linear ordering problem
- scientific article; zbMATH DE number 1558221 (Why is no real title available?)
- The schedule-sequencing problem
- New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
- A semidefinite optimization approach to the target visitation problem
- A note on a proof of SPT optimality for single-machine sequencing problems via the transportation problem
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3320091)