A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines
From MaRDI portal
Publication:2434270
DOI10.1007/s10951-009-0154-4zbMath1280.68298OpenAlexW2025171042MaRDI QIDQ2434270
Yang Fang, Peihai Liu, Xi-wen Lu
Publication date: 5 February 2014
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10951-009-0154-4
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)
Related Items (27)
Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart ⋮ Online scheduling to minimize maximum weighted flow-time on a bounded parallel-batch machine ⋮ A best possible on-line algorithm for scheduling on uniform parallel-batch machines ⋮ Online scheduling on bounded batch machines to minimize the maximum weighted completion time ⋮ Online scheduling with delivery time on a bounded parallel batch machine with limited restart ⋮ Research on the parallel-batch scheduling with linearly lookahead model ⋮ 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 ⋮ Online scheduling of jobs with kind release times and deadlines on a single machine ⋮ Best possible algorithms for online scheduling on identical batch machines with periodic pulse interruptions ⋮ Online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead ⋮ Online scheduling on unbounded parallel-batch machines to minimize maximum flow-time ⋮ An on-line algorithm for the single machine unbounded parallel-batching scheduling with large delivery times ⋮ Online scheduling on the unbounded drop-line batch machines to minimize the maximum delivery completion time ⋮ Online scheduling on an unbounded parallel-batch machine and a standard machine to minimize makespan ⋮ Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan ⋮ Online over time scheduling on parallel-batch machines: a survey ⋮ The medical laboratory scheduling for weighted flow-time ⋮ Online batch scheduling with kind release times and incompatible families to minimize makespan ⋮ Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart ⋮ Online scheduling on unbounded parallel-batch machines with incompatible job families ⋮ A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints ⋮ Online batch scheduling on parallel machines with delivery times ⋮ Online scheduling on two uniform unbounded parallel-batch machines to minimize makespan ⋮ Online Algorithms for Scheduling Unit Length Jobs on Unbounded Parallel-Batch Machines with Linearly Lookahead ⋮ Online unbounded batch scheduling on parallel machines with delivery times
Cites Work
- Unnamed Item
- The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan
- An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines
- A best online algorithm for scheduling on two parallel batch machines
- Scheduling a batching machine
- Scheduling one batch processor subject to job release dates
- A note on the single machine serial batching scheduling problem to minimize maximum lateness with precedence constraints
- The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard
- Minimizing makespan on a single batching machine with release times and non-identical job sizes
- On-line algorithms for minimizing makespan on batch processing machines
- Efficient Algorithms for Scheduling Semiconductor Burn-In Operations
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Minimizing makespan on a single batch processing machine with dynamic job arrivals
- Scheduling a single batch processing machine with non-identical job sizes
- Single machine parallel batch scheduling subject to precedence constraints
This page was built for publication: A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines
