Optimal Scheduling of Tasks on Identical Parallel Processors

DOI10.1287/IJOC.7.2.191zbMATH Open0859.90081OpenAlexW2087245794MaRDI QIDQ4896446FDOQ4896446

Authors: Mauro Dell'Amico, Silvano Martello 

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

Recommendations

• scientific article; zbMATH DE number 1234084
• scientific article; zbMATH DE number 3941253
• A note on scheduling multiprocessor tasks with identical processing times.
• Scheduling malleable tasks on parallel processors to minimize the makespan
• A \(\frac 54\)-approximation algorithm for scheduling identical malleable tasks

zbMATH Keywords

lower boundsapproximation algorithmsschedulingbranch-and-boundidentical parallel processorsmaximum completion time

Mathematics Subject Classification ID

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

Cited In (62)

• Fast lifting procedures for the bin packing problem
• Optimal scheduling of progressive processing tasks
• Metaheuristics for the vehicle routing problem with loading constraints
• Exact solution techniques for two-dimensional cutting and packing
• Minimizing the makespan on two identical parallel machines with mold constraints
• Title not available (Why is that?)
• A characterization of optimal multiprocessor schedules and new dominance rules
• Minimizing the maximal ergonomic burden in intra-hospital patient transportation
• Routing problems with loading constraints
• Heuristic and exact algorithms for the multi-pile vehicle routing problem
• Exact algorithms for scheduling programs with shared tasks
• Rescheduling to minimize makespan on a changing number of identical processors
• Optimal read-once parallel disk scheduling
• A composite algorithm for multiprocessor scheduling
• A computational study of lower bounds for the two dimensional bin packing problem
• Identical parallel machine scheduling with assurance of maximum waiting time for an emergency job
• Bounds for the cardinality constrained \(P \|C_{max}\) problem
• Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem
• Scheduling parallel processors: Structural properties and optimal policies
• Partial solutions and multifit algorithm for multiprocessor scheduling
• Tight bounds for the identical parallel machine scheduling problem
• Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms
• An exact algorithm for parallel machine scheduling with conflicts
• Scheduling malleable tasks on parallel processors to minimize the makespan
• A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective
• Optimal allocation of requirements to parallel devices
• Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem
• Recent advances on two-dimensional bin packing problems
• Improved approaches to the exact solution of the machine covering problem
• A nonidentical parallel processor scheduling problem
• Improved algorithms to minimize workload balancing criteria on identical parallel machines
• Bin packing and cutting stock problems: mathematical models and exact algorithms
• The off-line group seat reservation problem
• Properties of some ILP formulations of a class of partitioning problems
• Maximizing the minimum completion time on parallel machines
• A local branching-based algorithm for the quay crane scheduling problem under unidirectional schedules
• A new destructive bounding scheme for the bin packing problem
• Two-dimensional packing problems: a survey
• Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration
• A stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts
• Two branch-and-bound algorithms for the robust parallel machine scheduling problem
• A note on scheduling multiprocessor tasks with identical processing times.
• Block rearranging elements within matrix columns to minimize the variability of the row sums
• Minimizing labor requirements in a periodic vehicle loading problem
• Tight bounds for the identical parallel machine‐scheduling problem: Part II
• PROPERTY OF THE OPTIMUM RELAXED SOLUTION FOR PROBLEM TO SCHEDULE INDEPENDENT TASKS ON UNRELATED PROCESSORS
• A new approach for bicriteria partitioning problem
• The complexity of finding Nash equilibria
• Minimizing makespan subject to minimum flowtime on two identical parallel machines
• Exact and approximate methods for a one-dimensional minimax bin-packing problem
• Task scheduling for multiunit parallel test using mixed-integer linear programming
• Title not available (Why is that?)
• Production scheduling of independent jobs on parallel identical processors
• An analysis of lower bound procedures for the bin packing problem
• Some algorithms of solving minimax multiprocessor scheduling problem
• A note on posterior tight worst-case bounds for longest processing time schedules
• Bee colony optimization for scheduling independent tasks to identical processors
• A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem
• Minimization of the number of devices under working in systems of identical parallel devices
• A branch, bound and remember algorithm for maximizing the production rate in the simple assembly line balancing problem
• Title not available (Why is that?)
• Makespan of a batch of partitionable tasks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4896446)