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