SINGLE MACHINE SCHEDULING WITH JOB DELIVERY TO MINIMIZE MAKESPAN

Lingfa Lu () and Jinjiang Yuan
Additional contact information
Lingfa Lu: Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People's Republic of China
Jinjiang Yuan: Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People's Republic of China

Asia-Pacific Journal of Operational Research (APJOR), 2008, vol. 25, issue 01, 1-10

Abstract: In the single machine scheduling problem with job delivery to minimize makespan, jobs are processed on a single machine and delivered by a capacitated vehicle to their respective customers. We first consider the special case with a single customer, that is, all jobs have the same transportation time. Chang and Lee (2004) proved that this case is strongly NP-hard. They also provided a heuristic with the worst-case performance ratio$\frac{5}{3}$, and pointed out that no heuristic can have a worst-case performance ratio less than$\frac{3}{2}$unlessP=NP. In this paper, we provide a new heuristic which has the best possible worst-case performance ratio$\frac{3}{2}$. We also consider an extended version in which the jobs have non-identical transportation times and the transportation time of a delivery batch is defined as the maximum transportation time of the jobs contained in it. We provide a heuristic with the worst-case performance ratio 2 for the extended version, and show that this bound is tight.

Keywords: Scheduling; job delivery; heuristic; worst-case performance ratio (search for similar items in EconPapers)
Date: 2008
References: View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595908001596
Access to full text is restricted to subscribers

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:wsi:apjorx:v:25:y:2008:i:01:n:s0217595908001596

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595908001596

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().