SINGLE MACHINE SCHEDULING WITH BATCH DELIVERY TO MULTIPLE CUSTOMERS IN A STAR-SHAPED NETWORK

Leiyang Wang () and Zhaohui Liu ()
Additional contact information
Leiyang Wang: Department of Mathematics, East China University of Science and Technology, Shanghai 200237, P. R. China
Zhaohui Liu: Department of Mathematics, East China University of Science and Technology, Shanghai 200237, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2013, vol. 30, issue 01, 1-9

Abstract: In this paper, we consider the scheduling problem in which the jobs are first processed on a single machine and then delivered in batches by a single vehicle with limited capacity to the respective customers located at the vertices of a star-shaped network. The goal is to minimize the makespan. We present a 3/2-approximation algorithm for the identical job size case and a 2-approximation algorithm for the non-identical job sizes case.

Keywords: Scheduling; batch delivery; star-shaped network; approximation algorithm (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595912500480
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:30:y:2013:i:01:n:s0217595912500480

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595912500480

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