Constructive heuristic algorithms for the open shop problem
From MaRDI portal
The \(m\)-machine open shop scheduling problem without preemption is considered. Two type of heuristic algorithms to minimize the maximum completion time (makespan) are proposed. Heuristics of the first type generate so-called rank-minimal schedules. Their time complexity varies from \(O((\max\{n,m\})^ 3\log(\max\{n,m\}))\) to \(O((\max\{n,m\})^ 4)\), where \(n\) is the number of jobs. The second type heuristic is a special restricted branch and bound algorithm. Its time complexity is \(O(n^ 2 m^ 2)\). Presented algorithms are tested on different benchmark problems.
Recommendations
- Heuristic constructive algorithms for open shop scheduling to minimize mean flow time
- A new heuristic for open shop total completion time problem
- Classical and new heuristics for the open-shop problem: A computational evaluation
- New efficient heuristics for scheduling open shops with makespan minimization
- scientific article; zbMATH DE number 4170622
Cites work
- Benchmarks for basic scheduling problems
- scientific article; zbMATH DE number 4170627 (Why is no real title available?)
- scientific article; zbMATH DE number 3708086 (Why is no real title available?)
- Insertion techniques for the heuristic solution of the job shop problem
- On the number of feasible schedules of the open-shop-problem-an application of special latin rectangles
- Open Shop Scheduling to Minimize Finish Time
- Tabu Search—Part I
Cited in
(48)- A greedy open shop heuristic with job priorities
- Classical and new heuristics for the open-shop problem: A computational evaluation
- A branch \(\&\) bound algorithm for the open-shop problem
- A tabu search algorithm for the open shop problem
- Competitive genetic algorithms for the open-shop scheduling problem
- Job-shop scheduling with processing alternatives.
- An efficient tabu search approach for the two-machine preemptive open shop scheduling problem.
- A hybrid genetic algorithm for the open shop scheduling problem
- Using intelligent backtracking to improve branch-and-bound methods: An application to Open-Shop problems
- A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size
- The total completion time open shop scheduling problem with a given sequence of jobs on one machine
- An effective heuristic algorithm for the partial shop scheduling problem
- A hybrid imperialist competitive algorithm for minimizing makespan in a multi-processor open shop
- Insertion techniques for the heuristic solution of the job shop problem
- Heuristics for permutation flow shop scheduling with batch setup times
- Scheduling two-machine preemptive open shops to minimize total completion time
- A branch \& bound method for the general-shop problem with sequence dependent setup-times
- Metaheuristics: A bibliography
- New efficient heuristics for scheduling open shops with makespan minimization
- Four decades of research on the open-shop scheduling problem to minimize the makespan
- Open shop scheduling problems with conflict graphs
- Benchmarks for basic scheduling problems
- Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop
- The representation of partially-concurrent open shop problems
- Heuristic constructive algorithms for open shop scheduling to minimize mean flow time
- An optimal constraint programming approach to the open-shop problem
- Two-machine open shop scheduling with secondary criteria
- Performance analysis of rotation schedule and improved strategy for open shop problem to minimise makespan
- Aggregation heuristic for the open-pit block scheduling problem
- SOLVING THE OPEN SHOP SCHEDULING PROBLEM VIA A HYBRID GENETIC-VARIABLE NEIGHBORHOOD SEARCH ALGORITHM
- scientific article; zbMATH DE number 4170622 (Why is no real title available?)
- scientific article; zbMATH DE number 4170627 (Why is no real title available?)
- A selecting method of reasonable non-dominated schedules on open shop
- Bounds and initial solutions for frame ineration in machine scheduling
- Dual criteria preemptive open-shop problems with minimum makespan
- scientific article; zbMATH DE number 1910710 (Why is no real title available?)
- scientific article; zbMATH DE number 938619 (Why is no real title available?)
- OSGA: genetic-based open-shop scheduling with consideration of machine maintenance in small and medium enterprises
- A heuristic algorithm for open-shop scheduling problems with a single server
- Stochastic Algorithms: Foundations and Applications
- Solving the open shop scheduling problem
- The LPT heuristic for minimizing total load on a proportionate openshop
- A genetic algorithm for scheduling open shops with conflict graphs to minimize the makespan
- On the open-shop problem with preemption and minimizing the average completion time
- Scheduling preemptive open shops to minimize total tardiness
- A contribution and new heuristics for open shop scheduling
- A new heuristic for open shop total completion time problem
- The museum visitor routing problem
This page was built for publication: Constructive heuristic algorithms for the open shop problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1310611)
