A (32+ε)-approximation algorithm for scheduling on two parallel machines with job delivery coordination

Yong Chen, An Zhang, Zhiyi Tan, Ying Xue and Guangting Chen

Journal of the Operational Research Society, 2021, vol. 72, issue 9, 1929-1942

Abstract: Integration of production and distribution operations at the scheduling level is one of the most important issues concerned in recent years in supply chain management. We investigate the scheduling problem with job delivery coordination. Concretely, we are given a set of jobs with non-identical processing times and non-identical sizes to be first processed by two parallel-identical machines and then delivered to a common customer by a single vehicle, which has a limited capacity that can carry up to a fixed total size of jobs in one batch. The objective is to minimize the makespan, ie, the time when all the jobs have reached the customer and the delivery vehicle has returned to the machine. The problem does not admit a polynomial time approximation algorithm with worst-case ratio smaller than 32 unless P = NP. By introducing some novel ideas and new methods, including algorithms solving multiple knapsack problem as subprocedures and the rediscovery of the profound nature of the bin-packing algorithm, we propose a polynomial time approximation algorithm with worst-case ratio arbitrary close to 32. The algorithm, acquired after long-term research containing many earlier related works, is the first algorithm for this kind of problems and its theoretical performance is nearly best.

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2019.1655204 (text/html)
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:taf:tjorxx:v:72:y:2021:i:9:p:1929-1942

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2019.1655204

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().