On some geometric methods in scheduling theory: A survey

DOI10.1016/0166-218X(94)90036-1zbMath0809.90082MaRDI QIDQ1337673

Sergey Sevast'janov

Publication date: 3 April 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-hardapproximation algorithmsjob shopsclosed walkflow shopspolynomial running time

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches, Maximum Inequalities for Rearrangements of Summands and Assignments of Signs, Approximation and online algorithms for multidimensional bin packing: a survey, A fluid approach to large volume job shop scheduling, A note on the two-stage assembly flow shop scheduling problem with uniform parallel machines, The Open Shop Scheduling Problem, Unnamed Item, Reroute sequence planning in telecommunication networks and compact vector summation., Concurrent flowshop scheduling to minimize makespan., Grouping techniques for scheduling problems: simpler and faster, Complexity, bounds and dynamic programming algorithms for single track train scheduling, Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem, Scheduling jobshops with some identical or similar jobs, Vector summation within minimal angle, On some properties of optimal schedules in the job shop problem with preemption and an arbitrary regular criterion, Scheduling of a single crane in batch annealing process, The flow shop problem with no-idle constraints: a review and approximation, Rearrangements of series, A linear time approximation algorithm for permutation flow shop scheduling, Heuristics for the two-stage job shop scheduling problem with a bottleneck machine, A hybrid genetic algorithm for the open shop scheduling problem, Flexible flow shop scheduling with uniform parallel machines, Performance guarantees for flowshop heuristics to minimize makespan

Cites Work

• An approximate algorithm for the three-machine problem
• ``Integer-making theorems
• Minimization of the production line work cycle
• Scheduling a three-machine job shop
• Optimal two- and three-stage production schedules with setup times included
• The Steinitz constant of the plane.
• Bounding algorithm for the routing problem with arbitrary paths and alternative servers
• A Vector-Sum Theorem and its Application to Improving Flow Shop Guarantees
• Open Shop Scheduling to Minimize Finish Time
• An Algorithm for the Open-Shop Problem
• Vector Summation in Banach Space and Polynomial Algorithms for Flow Shops and Open Shops
• A Non-Numerical Approach to Production Scheduling Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item