A tight approximation algorithm for problem $$P2\rightarrow D|v=1,c=1|C_{\max }$$P2→D|v=1,c=1|Cmax

Yinling Wang (), Yan Lan (), Xin Chen (), Xin Han () and Yong Piao ()
Additional contact information
Yinling Wang: Dalian University of Technology
Yan Lan: Dalian Minzu University
Xin Chen: Liaoning University of Technology
Xin Han: Dalian University of Technology
Yong Piao: Dalian University of Technology

Journal of Combinatorial Optimization, No 0, 12 pages

Abstract: Abstract This paper focuses on the scheduling problem on two parallel machines with delivery coordination. In particular, given a set of n jobs, we aim to find a schedule with a minimal makespan such that all jobs are first executed on two parallel machines then delivered at the destination with a transporter. This problem is known to be NP-hard Chang and Lee (Eur J Oper Res 158(2):470–487, 2004), cannot be solved with an approximation ratio strictly less than 3/2 unless P=NP. We close the gap by proposing a polynomial time algorithm whose approximation ratio is $$3/2+\varepsilon $$3/2+ε with $$\varepsilon >0$$ε>0, improve the previous best ratio $$14/9 + \epsilon $$14/9+ϵ.

Keywords: Scheduling with transportation; Bin packing; Approximation algorithm (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00593-1 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::y::i::d:10.1007_s10878-020-00593-1

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

DOI: 10.1007/s10878-020-00593-1

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 ().