Approximation algorithms in batch processing

DOI10.1023/A:1027316504440zbMath1053.90033OpenAlexW238776573MaRDI QIDQ1417850

Chung Keung Poon, Xiaotie Deng, Yu-Zhong Zhang

Publication date: 6 January 2004

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1027316504440

zbMATH Keywords

batchschedulingmakespanrelease timeon-line

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

Online parallel-batch scheduling to minimize total weighted completion time on single unbounded machine ⋮ Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart ⋮ On-line scheduling on an unbounded parallel batch machine to minimize makespan of two families of jobs ⋮ A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times ⋮ Optimal Semi-Online Algorithm for Scheduling on Two Parallel Batch Processing Machines ⋮ 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 ⋮ On-line scheduling with rejection on identical parallel machines ⋮ Semi-online scheduling: a survey ⋮ An optimal online algorithm for the parallel-batch scheduling with job processing time compatibilities ⋮ Optimal on-line algorithms for one batch machine with grouped processing times ⋮ Parallel-batch scheduling with rejection: structural properties and approximation algorithms ⋮ Online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead ⋮ Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities ⋮ 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 ⋮ An improved on-line algorithm for single parallel-batch machine scheduling with delivery times ⋮ Online scheduling of equal-length jobs with incompatible families on multiple batch machines to maximize the weighted number of early jobs ⋮ Scheduling jobs with release dates on parallel batch processing machines to minimize the makespan ⋮ A two stage scheduling with transportation and batching ⋮ Online scheduling on an unbounded parallel-batch machine and a standard machine to minimize makespan ⋮ An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan ⋮ Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan ⋮ A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan ⋮ On-line scheduling on a batch machine to minimize makespan with limited restarts ⋮ Online over time scheduling on parallel-batch machines: a survey ⋮ Scheduling a bounded parallel-batching machine with incompatible job families and rejection ⋮ Online batch scheduling with kind release times and incompatible families to minimize makespan ⋮ A coordination mechanism for a scheduling game with parallel-batching machines ⋮ Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan ⋮ Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart ⋮ Online scheduling of incompatible unit-length job families with lookahead ⋮ Online scheduling on unbounded parallel-batch machines with incompatible job families ⋮ Best semi-online algorithms for unbounded parallel batch scheduling ⋮ Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan ⋮ Parallel-machine parallel-batching scheduling with family jobs and release dates to minimize makespan ⋮ On-line scheduling algorithms for a batch machine with finite capacity ⋮ Online batch scheduling on parallel machines with delivery times ⋮ Optimal online-list batch scheduling ⋮ Online scheduling on unbounded parallel-batch machines to minimize the makespan ⋮ Single machine batch scheduling with release times ⋮ An asymptotic PTAS for batch scheduling with nonidentical job sizes to minimize makespan ⋮ On-line scheduling with delivery time on a single batch machine ⋮ Online scheduling in a parallel batch processing system to minimize makespan using restarts ⋮ THE NP-HARDNESS OF MINIMIZING THE TOTAL LATE WORK ON AN UNBOUNDED BATCH MACHINE ⋮ Scheduling jobs with release dates on parallel batch processing machines ⋮ OPTIMAL SEMI-ONLINE ALGORITHM FOR SCHEDULING ON A BATCH PROCESSING MACHINE ⋮ Online scheduling on two uniform unbounded parallel-batch machines to minimize makespan ⋮ A PTAS for parallel batch scheduling with rejection and dynamic job arrivals ⋮ Scheduling an unbounded batching machine with job processing time compatibilities ⋮ On-line scheduling of unit time jobs with rejection on uniform machines ⋮ Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead ⋮ Online Algorithms for Scheduling Unit Length Jobs on Unbounded Parallel-Batch Machines with Linearly Lookahead ⋮ Online algorithms to schedule a proportionate flexible flow shop of batching machines ⋮ An Online Scheduling Problem on a Drop-Line Parallel Batch Machine with Delivery Times and Limited Restart ⋮ Online unbounded batch scheduling on parallel machines with delivery times