Optimal Scheduling of Tasks on Identical Parallel Processors

DOI10.1287/ijoc.7.2.191zbMath0859.90081OpenAlexW2087245794MaRDI QIDQ4896446

Publication date: 25 March 1997

Published in: ORSA Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.7.2.191

zbMATH Keywords

scheduling branch-and-bound lower bounds approximation algorithms maximum completion time identical parallel processors

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 (41)

Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem ⋮ A characterization of optimal multiprocessor schedules and new dominance rules ⋮ An analysis of lower bound procedures for the bin packing problem ⋮ Metaheuristics for the vehicle routing problem with loading constraints ⋮ Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms ⋮ Bin packing and cutting stock problems: mathematical models and exact algorithms ⋮ A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem ⋮ Improved algorithms to minimize workload balancing criteria on identical parallel machines ⋮ Improved approaches to the exact solution of the machine covering problem ⋮ An exact algorithm for parallel machine scheduling with conflicts ⋮ Exact and approximate methods for a one-dimensional minimax bin-packing problem ⋮ Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem ⋮ A stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts ⋮ A new destructive bounding scheme for the bin packing problem ⋮ Routing problems with loading constraints ⋮ The off-line group seat reservation problem ⋮ Identical parallel machine scheduling with assurance of maximum waiting time for an emergency job ⋮ Tight bounds for the identical parallel machine‐scheduling problem: Part II ⋮ Partial solutions and multifit algorithm for multiprocessor scheduling ⋮ A note on posterior tight worst-case bounds for longest processing time schedules ⋮ Minimizing the makespan on two identical parallel machines with mold constraints ⋮ Heuristic and exact algorithms for the multi-pile vehicle routing problem ⋮ Minimizing the maximal ergonomic burden in intra-hospital patient transportation ⋮ Block rearranging elements within matrix columns to minimize the variability of the row sums ⋮ Bee colony optimization for scheduling independent tasks to identical processors ⋮ Two branch-and-bound algorithms for the robust parallel machine scheduling problem ⋮ Recent advances on two-dimensional bin packing problems ⋮ A composite algorithm for multiprocessor scheduling ⋮ Bounds for the cardinality constrained \(P \|C_{max}\) problem ⋮ Minimizing labor requirements in a periodic vehicle loading problem ⋮ Minimizing makespan subject to minimum flowtime on two identical parallel machines ⋮ Unnamed Item ⋮ Exact solution techniques for two-dimensional cutting and packing ⋮ A local branching-based algorithm for the quay crane scheduling problem under unidirectional schedules ⋮ Properties of some ILP formulations of a class of partitioning problems ⋮ Maximizing the minimum completion time on parallel machines ⋮ Two-dimensional packing problems: a survey ⋮ Tight bounds for the identical parallel machine scheduling problem ⋮ Fast lifting procedures for the bin packing problem ⋮ A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective ⋮ A new approach for bicriteria partitioning problem

This page was built for publication: Optimal Scheduling of Tasks on Identical Parallel Processors