Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

Parallel Machine Scheduling with a Single Server: Loading and Unloading

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 8287))

  • 1274Accesses

Abstract

This paper addresses the non-preemptive scheduling on two parallel identical machines sharing a single server in charge of loading and unloading jobs. Each job has to be loaded by the server before being processed on one of the machines and unloaded immediately by the server after its processing. The goal is to minimize the makespan. This paper considers classical algorithmsLS andLPT for the problem where the loading and unloading times both are equal to one time unit. We first analyze the structure of list scheduling for the problem and then show that the tight worst case ratios ofLS andLPT are 12/7 and 4/3, respectively. Finally, we provide a proof of computational complexity for the problem.

Supported by the National Natural Science Foundation of China (11001242, 11071220) and Zhejiang Province Natural Science Foundation of China (LY13A010015).

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Abdekhodaee, A.H., Wirth, A.: Scheduling parallel machines with a single server: some solvable cases and heuristics. Computers and Operations Research 29, 295–315 (2002)

    Article MathSciNet MATH  Google Scholar 

  2. Abdekhodaee, A.H., Wirth, A., Gan, H.S.: Equal processing and equal setup time cases of scheduling parallel machines with a single server. Computers and Operations Research 31, 1867–1889 (2004)

    Article MATH  Google Scholar 

  3. Abdekhodaee, A.H., Wirth, A., Gan, H.S.: Scheduling parallel machines with a single server: the general case. Computers and Operations Research 33, 994–1009 (2006)

    Article MathSciNet MATH  Google Scholar 

  4. Brucker, P., Dhaenens-Flipo, C., Knust, S., Kravchenko, S.A., Werner, F.: Complexity results for parallel machine problems with a single server. Journal of Scheduling 5, 429–457 (2002)

    Article MathSciNet MATH  Google Scholar 

  5. Brucker, P., Knust, S., Wang, G.: Complexity results for flow-shop problems with a single server. European Journal of Operational Research 165, 398–407 (2005)

    Article MathSciNet MATH  Google Scholar 

  6. Cheng, T.C.E., Kovalyov, M.: Scheduling a single server in a two-machine flow shop. Computing 70, 167–180 (2003)

    Article MathSciNet MATH  Google Scholar 

  7. Graham, R.: Bounds for certain multiprocessing anomalies. Bell System Technical Journal 45, 1563–1581 (1966)

    Article MATH  Google Scholar 

  8. Hall, N.G., Potts, C.N., Sriskandarajah, C.: Parallel machine scheduling with a common server. Discrete Applied Mathematics 102, 223–243 (2000)

    Article MathSciNet MATH  Google Scholar 

  9. Iravani, S., Teo, C.: Asymptotically optimal schedules for single-server flow shop problems with setup costs and times. Operations Research Letters 33, 421–430 (2005)

    Article MathSciNet MATH  Google Scholar 

  10. Jiang, Y., Dong, J., Ji, M.: Preemptive scheduling on two parallel machines with a single server. Computers & Industrial Engineering 66, 514–518 (2013)

    Article  Google Scholar 

  11. Kravchenko, S.A., Werner, F.: Parallel machine scheduling problems with a single server. Mathematical and Computer Modelling 26, 1–11 (1997)

    Article MathSciNet MATH  Google Scholar 

  12. Ou, J., Qi, X., Lee, C.: Parallel machine scheduling with multiple unloading servers. Journal of Scheduling 13, 213–226 (2010)

    Article MathSciNet MATH  Google Scholar 

  13. Su, L., Lee, Y.: The two-machine flowshop no-wait scheduling problem with a single server to minimize the total completion time. Computers & Operations Research 35, 2952–2963 (2008)

    Article MathSciNet MATH  Google Scholar 

  14. Su, C.: Online LPT algorithms for parallel machines scheduling with a single server. Journal of Combnatorial Optimization (2012), doi:10.1007/s10878-011-9441-z

    Google Scholar 

  15. Wang, G., Cheng, T.C.E.: An approximation algorithm for parallel machine scheduling with acommon server. Journal of the Operational Research Society 52, 234–237 (2001)

    Article MATH  Google Scholar 

  16. Werner, F., Kravchenko, S.A.: Scheduling with multiple servers. Automation and Remote Control 71(10), 2109–2121 (2010)

    Article MathSciNet MATH  Google Scholar 

  17. Xie, X., Li, Y., Zhou, H., Zheng, Y.: Scheduling parallel machines with a single server. In: Proceeding of International Conference on Measurement, Information and Control, vol. 1, pp. 453–456 (2012)

    Google Scholar 

  18. Xie, X., Zheng, Y., Li, Y.: Scheduling parallel machines with a Single Server: A Dedicated Case. In: Proceedings of Fifth International Joint Conference on Computational Sciences and Optimization, pp. 146–149 (2012)

    Google Scholar 

  19. Yip, Y., Cheng, C., Low, C.: Sequencing of an M machine flow shop with setup, processing and removal times separated. International Journal of Advanced Manufacturing Technology 30, 286–296 (2006)

    Article  Google Scholar 

  20. Zhang, L., Andrew, W.: On-line scheduling of two parallel machines with a single server. Computers and Operations Research 36, 1529–1553 (2009)

    Article MathSciNet MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou, 310018, China

    Jueliang Hu, Qinghui Zhang, Jianming Dong & Yiwei Jiang

Authors
  1. Jueliang Hu

    You can also search for this author inPubMed Google Scholar

  2. Qinghui Zhang

    You can also search for this author inPubMed Google Scholar

  3. Jianming Dong

    You can also search for this author inPubMed Google Scholar

  4. Yiwei Jiang

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institute of Theoretical Computer Science, ETH Zürich, Zürich, Switzerland

    Peter Widmayer

  2. State Key Lab for Manufacturing Systems Engineering, 710049, Xi’an, China

    Yinfeng Xu

  3. Department of Computer Science, Montana State University, 59717-3880, Bozeman, MT, USA

    Binhai Zhu

Rights and permissions

Copyright information

© 2013 Springer International Publishing Switzerland

About this paper

Cite this paper

Hu, J., Zhang, Q., Dong, J., Jiang, Y. (2013). Parallel Machine Scheduling with a Single Server: Loading and Unloading. In: Widmayer, P., Xu, Y., Zhu, B. (eds) Combinatorial Optimization and Applications. COCOA 2013. Lecture Notes in Computer Science, vol 8287. Springer, Cham. https://doi.org/10.1007/978-3-319-03780-6_10

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only


[8]ページ先頭

©2009-2025 Movatter.jp