Unbounded parallel-batch scheduling with drop-line tasks

Yuan Gao, Jinjiang Yuan () and Zhigang Wei
Additional contact information
Yuan Gao: Zhengzhou University
Jinjiang Yuan: Zhengzhou University
Zhigang Wei: Zhengzhou XindaJiean Information Technology Co., Ltd.

Journal of Scheduling, 2019, vol. 22, issue 4, No 5, 449-463

Abstract: Abstract In this paper, we study unbounded parallel-batch scheduling with drop-line tasks to minimize a regular objective function, where by “drop-line tasks” we mean that the completion time of each task (job) is equal to the sum of the starting time of the batch containing the task and the processing time of the task. In the problems considered in this paper, we assume that the tasks have individual release dates and the general regular objective function to be minimized is either of the sum-form or of the max-form. We then study the computational complexity of these problems on an unbounded parallel-batch processor. We show that (i) the problems are binary NP-hard and are solvable in pseudo-polynomial times, and (ii) when the number of processing times or release dates is a constant, the problems are solvable in polynomial times. We also point out some consequences of approximation algorithms.

Keywords: Parallel-batch scheduling; Drop-line tasks; Release dates; Computational complexity (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-018-0586-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:22:y:2019:i:4:d:10.1007_s10951-018-0586-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-018-0586-9

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().