Single-server parallel-machine scheduling with loading and unloading times

Yiwei Jiang (), Qinghui Zhang, Jueliang Hu, Jianming Dong and Min Ji
Additional contact information
Yiwei Jiang: Zhejiang Sci-Tech University
Qinghui Zhang: Zhejiang Sci-Tech University
Jueliang Hu: Zhejiang Sci-Tech University
Jianming Dong: Zhejiang Sci-Tech University
Min Ji: Zhejiang Gongshang University

Journal of Combinatorial Optimization, 2015, vol. 30, issue 2, No 1, 213 pages

Abstract: Abstract We consider a scheduling problem in which jobs are processed on two identical parallel machines that share a common server that loads and unloads jobs on them. Each job has to be loaded by the server before being processed on one of the machines and unloaded immediately by the server after its processing. The goal is to minimize the makespan. We study non-preemptive variants of the problem where the loading and unloading times are both equal to one time unit. Since the non-preemptive variant of the problem is NP-hard, we apply two classical heuristics, namely list scheduling (LS) and longest processing time (LPT),to tackle the problem. We show that LS and LPT have tight worst-case ratios of 12/7 and 4/3, respectively.

Keywords: Scheduling; Server; Algorithm; Worst-case ratio; Makespan (search for similar items in EconPapers)
Date: 2015
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/s10878-014-9727-z 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:jcomop:v:30:y:2015:i:2:d:10.1007_s10878-014-9727-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9727-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

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