Decomposition approaches in permutation scheduling problems with application to the M-machine flow shop scheduling problems
Three different decomposition approaches are described for permutation schedules. The first, Complete decomposition, gives conditions when a scheduling problem can be decomposed into two or more scheduling problems that ca be solved separately and then recomposed. Except for some single machine scheduling problems and a few cases of other problems, it is unlikely that these conditions will be satisfied. A Partial decomposition may be employed if the Complete decomposition fails. This requires a subset enumeration procedure along with a partial satisfaction of the conditions specified before. The majority of NP-complete scheduling problems will not meet the conditions necessary to employ either of the above decompositions. In this case branch and bound can be used as a decomposition tool (Iterative decomposition). Algorithms are developed that provide upper bounds, lower bounds, branching rules as well as a heuristic estimate of the lower bound. This branch and bound decomposition approach is then implemented on the M-machine flow problem. The algorithm developed, efficiently finds optimal solutions to small flow shop problems (5 jobs/5 machines). Since the variance of CPU times required to use this algorithm is high, two heuristic algorithms are suggested. These algorithms either heuristically fathom nodes or terminate early. Their CPU times are small compared to the optimal algorithm and they provide schedules almost as good, and are therefore viewed as a practical alternative.
- A computational study of the permutation flow shop problem based on a tight lower bound
- Applying machine based decomposition in 2-machine flow shops
- Decomposition in single-machine scheduling
- On non-permutation solutions to some two machine flow shop scheduling problems
- scientific article; zbMATH DE number 2050744
- A Comparative Study of Flow-Shop Algorithms
- A Functional Heuristic Algorithm for the Flowshop Scheduling Problem
- A General Bounding Scheme for the Permutation Flow-Shop Problem
- A Heuristic Algorithm for the n Job, m Machine Sequencing Problem
- An adaptive branching rule for the permutation flow-shop problem
- An Evaluation of Flow Shop Sequencing Heuristics
- Decomposition approaches in permutation scheduling problems with application to the M-machine flow shop scheduling problems
- Elimination methods in them ×n sequencing problem
- scientific article; zbMATH DE number 2146482 (Why is no real title available?)
- Letter to the Editor—An Experimental Investigation and Comparative Evaluation of Flow-Shop Scheduling Techniques
- ON THE USE OF DECOMPOSITION APPROACHES IN A SINGLE MACHINE SCHDULING PROBLEM
- Optimal two- and three-stage production schedules with set-up time included
- The Complexity of Flowshop and Jobshop Scheduling
- TWO-MACHINE SCHEDULING UNDER REQUIRED PRECEDENCE AMONG JOBS
- A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size
- Decomposition algorithms for synchronous flow shop problems with additional resources and setup times
- Heuristics for permutation flow shop scheduling with batch setup times
- Heuristic methods and applications: A categorized survey
- A problem reduction and decomposition approach for scheduling for a flowshop of batch processing machines
- Decomposition approaches in permutation scheduling problems with application to the M-machine flow shop scheduling problems
- A decomposition scheduling method for operating flexible manufacturing systems
- Decomposition heuristics for the hybrid flexible flowshop with transportation times
- On the heuristic solution of the permutation flow shop problem by path algorithms
This page was built for publication: Decomposition approaches in permutation scheduling problems with application to the M-machine flow shop scheduling problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2265944)
