Single machine scheduling with job delivery to multiple customers

Jianming Dong, Xueshi Wang, Jueliang Hu and Guohui Lin ()
Additional contact information
Jianming Dong: Zhejiang Sci-Tech University
Xueshi Wang: Zhejiang Sci-Tech University
Jueliang Hu: Zhejiang Sci-Tech University
Guohui Lin: Zhejiang Sci-Tech University

Journal of Scheduling, 2018, vol. 21, issue 3, No 6, 337-348

Abstract: Abstract We investigate a single machine scheduling problem with job delivery to multiple customers. In this problem, each job needs to be processed on the single machine, and then delivered by a single vehicle to its customer, where the job has a physical size representing the fraction of space it occupies on the vehicle. The vehicle delivers a shipment from the machine to a customer and has to return back to the machine for delivering the next shipment. It takes different constant time for the round trips between the machine and the different customers. The goal is to minimize the makespan, by that time all the jobs are processed and delivered to their respective customers, and the vehicle returns back to the machine. We propose a 2-approximation algorithm for the general case; when there are only two customers, we present an improved 5/3-approximation algorithm. The design and performance analysis of these two algorithms integrate several known results and techniques for the single machine scheduling problem, the bin-packing problem, and the knapsack problem.

Keywords: Single machine scheduling; Job delivery; Bin-packing; Knapsack; Approximation algorithm (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-017-0508-2 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:jsched:v:21:y:2018:i:3:d:10.1007_s10951-017-0508-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-017-0508-2

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

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