An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan

DOI10.1016/j.orl.2013.01.003zbMath1286.90054OpenAlexW1979238414MaRDI QIDQ2450605

Yanyan Li

Publication date: 14 May 2014

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2013.01.003

zbMATH Keywords

competitive ratioonline schedulingparallel-batch machineincompatible job families

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (12)

Online algorithms for scheduling on batch processing machines with interval graph compatibilities between jobs ⋮ An optimal online algorithm for the parallel-batch scheduling with job processing time compatibilities ⋮ Online Batch Scheduling of Incompatible Job Families with Variable Lookahead Interval ⋮ An on-line \textit{seru} scheduling algorithm with proactive waiting considering resource conflicts ⋮ A Production Plan Considering Parallel Machines and Deteriorating Effects: Minimizing the Makespan in the Section of Steel Box Girder Processing ⋮ Online Parallel-Batch Scheduling of Learning Effect Jobs with Incompatible Job Families for Prefabricated Components ⋮ Online over time scheduling on parallel-batch machines: a survey ⋮ Online batch scheduling with kind release times and incompatible families to minimize makespan ⋮ Online scheduling of incompatible unit-length job families with lookahead ⋮ Online Scheduling of Incompatible Family Jobs with Equal Length on an Unbounded Parallel-Batch Machine with Job Delivery ⋮ Single-machine batch scheduling with job processing time compatibility ⋮ Online scheduling of two-machine flowshop with lookahead and incompatible job families

Cites Work

• On-line scheduling on an unbounded parallel batch machine to minimize makespan of two families of jobs
• Scheduling a batching machine
• Approximation algorithms in batch processing
• A flexible on-line scheduling algorithm for batch machine with infinite capacity
• Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times
• Minimizing makespan in batch machine scheduling
• On-line algorithms for minimizing makespan on batch processing machines
• The Batch Loading and Scheduling Problem
• Minimizing makespan on a single batch processing machine with dynamic job arrivals

This page was built for publication: An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan