Online scheduling with delivery time on a bounded parallel batch machine with limited restart
type: Item
instance of: scholarly article
title: Online scheduling with delivery time on a bounded parallel batch machine with limited restart
zbMATH Open document ID: 1394.90287
DOI: 10.1155/2015/628254
author: Hailing Liu
author: Long Wan
author: Zhigang Yan
author: Jinjiang Yuan
published in: Mathematical Problems in Engineering
publication date: 2018-08-27T00:00:00Z
review text: Summary: We consider the online (over time) scheduling of equal length jobs on a bounded parallel batch machine with batch capacity \(b\) to minimize the time by which all jobs have been delivered with limited restart. Here, ``restart'' means that a running batch may be interrupted, losing all the work done on it, and jobs in the interrupted batch are then released and become independently unscheduled jobs, called restarted jobs. ``Limited restart'' means that a running batch which contains some restarted jobs cannot be restarted again. When \(b = 2\), we propose a best possible online algorithm \(H(b = 2)\) with a competitive ratio of \(1 + \alpha\), where \(\alpha\) is the positive solution of \(2 \alpha(1 + \alpha) = 1\). When \(b \geq 3\), we present a best possible online algorithm \(H(b \geq 3)\) with a competitive ratio of \(1 + \beta\), where \(\beta\) is the positive solution of \(\beta(1 + \beta)^2 = 1\).
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 6926842
Wikidata QID: Q59119166
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2015/628254
OpenAlex ID: W1518664282
cites work: On-line scheduling on a single machine: Maximizing the number of early jobs
cites work: Restarts can help in the on-line minimization of the maximum delivery time on a single machine
cites work: Lower bounds for on-line single-machine scheduling.
cites work: Minimizing the total completion time on-line on a single machine, using restarts
cites work: A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan
cites work: On-line scheduling on a batch machine to minimize makespan with limited restarts
cites work: Approximation algorithms in batch processing
cites work: Minimizing makespan on a single batch processing machine with nonidentical job sizes
cites work: On-line scheduling algorithms for a batch machine with finite capacity
cites work: A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines
cites work: Online scheduling on unbounded parallel-batch machines to minimize the makespan
cites work: On-line scheduling with delivery time on a single batch machine
cites work: A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times
cites work: Optimal on-line algorithms for one batch machine with grouped processing times
cites work: An improved on-line algorithm for single parallel-batch machine scheduling with delivery times
cites work: Online unbounded batch scheduling on parallel machines with delivery times
cites work: Online scheduling in a parallel batch processing system to minimize makespan using restarts
cites work: Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan
cites work: Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart
description: scientific article; zbMATH DE number 6926842