Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-05T12:46:55.657Z Has data issue: false hasContentIssue false
  • English
  • Français

PARALLEL MACHINE SCHEDULING WITH JOB DELIVERY COORDINATION

Part of: Operations research and management science

Published online by Cambridge University Press:  25 May 2017

J. M. DONG Open the ORCID record for J. M. DONG [Opens in a new window] ,
X. S. WANG ,
L. L. WANG  and
J. L. HU Open the ORCID record for J. L. HU [Opens in a new window]
J. M. DONG
Affiliation:
School of Sciences, Zhejiang Sci-Tech University, Hangzhou 310018, China email [email protected] email [email protected]
X. S. WANG
Affiliation:
Department of Commodity, Yongan Futures Co. Ltd, Hangzhou 310000, China email [email protected]
L. L. WANG
Affiliation:
College of Automation, Hangzhou Dianzi University, Hangzhou 310018, China email [email protected]
J. L. HU*
Affiliation:
School of Sciences, Zhejiang Sci-Tech University, Hangzhou 310018, China email [email protected] email [email protected]
*
✉[email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We analyse a parallel (identical) machine scheduling problem with job delivery to a single customer. For this problem, each job needs to be processed on $m$ parallel machines non-pre-emptively and then transported to a customer by one vehicle with a limited physical capacity. The optimization goal is to minimize the makespan, the time at which all the jobs are processed and delivered and the vehicle returns to the machine. We present an approximation algorithm with a tight worst-case performance ratio of $7/3-1/m$ for the general case, $m\geq 3$.

Keywords

schedulingjob deliverybin packingapproximation algorithm

MSC classification

Primary: 90B35: Scheduling theory, deterministic
Secondary: 90C27: Combinatorial optimization
Type
Research Article
Information
The ANZIAM Journal , Volume 58 , Issue 3-4 , April 2017 , pp. 306 - 313
Copyright
© 2017 Australian Mathematical Society 

References

Chang, Y.-C. and Lee, C.-Y., “Machine scheduling with job delivery coordination”, European J. Oper. Res. 158 (2004) 470–487; doi:10.1016/S0377-2217(03)00364-3.Google Scholar
Dósa, G., Li, R., Han, X. and Tuza, Zs., “Tight absolute bound for first fit decreasing bin-packing: $\text{FFD}(L)\leq (11/9)\text{OPT}(L)+6/9$ ”, Theoret. Comput. Sci. 510 (2013) 13–61; doi:10.1016/j.tcs.2013.09.007.Google Scholar
Graham, R. L., “Bounds for certain multiprocessing anomalies”, Bell Syst. Tech. J. 45 (1966) 1563–1581; doi:10.1002/j.1538-7305.1966.tb01709.x.Google Scholar
He, Y., Zhong, W. Y. and Gu, H., “Improved algorithms for two single machine scheduling problems”, Theoret. Comput. Sci. 363 (2006) 257–265; doi:10.1016/j.tcs.2006.04.014.Google Scholar
Lu, L. F. and Yuan, J. J., “Single machine scheduling with job delivery to minimize makespan”, Asia-Pac. J. Oper. Res. 25 (2008) 1–10; doi:10.1142/S0217595908001596.Google Scholar
Simchi-Levi, D., “New worst-case results for the bin packing problem”, Naval Res. Logist. 41 (1994) 579–585; doi:10.1002/1520-6750(199406)41:4 <579::AID-NAV3220410409 >3.0.CO;2-G .Google Scholar
Su, C.-S., Pan, J. C.-H. and Hsu, T.-S., “A new heuristic algorithm for the machine scheduling problem with job delivery coordination”, Theoret. Comput. Sci. 410 (2009) 2581–2591; doi:10.1016/j.tcs.2009.02.019.CrossRefGoogle Scholar
Zhong, W. Y., Dósa, G. and Tan, Z. Y., “On the machine scheduling problem with job delivery coordination”, European J. Oper. Res. 182 (2007) 1057–1072; doi:10.1016/j.ejor.2006.09.059.Google Scholar