A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective

DOI10.1016/0305-0548(94)90053-1zbMath0797.90043OpenAlexW2049418901MaRDI QIDQ1318519

Gilbert Laporte, Felipe M. Müller, Michel Gendreau, Paulo Morelato França

Publication date: 25 October 1994

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0305-0548(94)90053-1

zbMATH Keywords

makespanheuristicidentical parallel machinesnear-optimal solutions

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

List scheduling algorithms to minimize the makespan on identical parallel machines, Improved approaches to the exact solution of the machine covering problem, An exact algorithm for parallel machine scheduling with conflicts, The longest processing time rule for identical parallel machines revisited, Tight bounds for the identical parallel machine‐scheduling problem: Part II, Partial solutions and multifit algorithm for multiprocessor scheduling, Minimizing the makespan in nonpreemptive parallel machine scheduling problem, A composite algorithm for multiprocessor scheduling, Minimizing labor requirements in a periodic vehicle loading problem, Heuristics for a two-stage hybrid flowshop scheduling problem with ready times and a product-mix ratio constraint, Heuristics for online scheduling on identical parallel machines with two GoS levels, Tight bounds for the identical parallel machine scheduling problem, Machine scheduling models in environmentally focused chemical manufacturing

Cites Work

• Unnamed Item
• Unnamed Item
• A state-of-the-art review of parallel-machine scheduling research
• Heuristic algorithms for the multiple knapsack problem
• Improved 0/1-interchange scheduling
• Bin packing with restricted piece sizes
• A linear time approximation algorithm for multiprocessor scheduling
• Tighter Bounds for the Multifit Processor Scheduling Algorithm
• Evaluation of a MULTIFIT-based scheduling algorithm
• Tighter Bounds for LPT Scheduling on Uniform Processors
• The pfort verifier
• Scheduling with earliest start and due date constraints on multiple machines
• Algorithms for Scheduling Independent Tasks
• An Application of Bin-Packing to Multiprocessor Scheduling
• `` Strong NP-Completeness Results
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Optimal Scheduling of Tasks on Identical Parallel Processors
• Bounds on Multiprocessing Timing Anomalies