IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v68y2017i4d10.1007_s10898-017-0509-x.html
   My bibliography  Save this article

Parallel machine scheduling with general sum of processing time based models

Author

Listed:
  • Radosław Rudek

    (Wrocław University of Economics)

Abstract

In this paper, we analyse the parallel machine makespan minimization problem with the general sum of processing time based learning or aging effects. First, we prove that an optimal solution to the single machine case can be found by priority rules. Next, for the considered parallel machine problem, we construct the exact dynamic programming algorithm that can operate on real-valued job processing times, which is the only exact algorithm for the analysed problem. The computational analysis confirms that it can solve optimally moderate problem instances.

Suggested Citation

  • Radosław Rudek, 2017. "Parallel machine scheduling with general sum of processing time based models," Journal of Global Optimization, Springer, vol. 68(4), pages 799-814, August.
    • Handle: RePEc:spr:jglopt:v:68:y:2017:i:4:d:10.1007_s10898-017-0509-x
    DOI: 10.1007/s10898-017-0509-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-017-0509-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-017-0509-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Abbasali Jafari & Ghasem Moslehi, 2012. "Scheduling linear deteriorating jobs to minimize the number of tardy jobs," Journal of Global Optimization, Springer, vol. 54(2), pages 389-404, October.
    2. Lai, Peng-Jen & Lee, Wen-Chiung, 2011. "Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects," Omega, Elsevier, vol. 39(5), pages 467-471, October.
    3. Wu, Chin-Chia & Lee, Wen-Chiung, 2009. "A note on the total completion time problem in a permutation flowshop with a learning effect," European Journal of Operational Research, Elsevier, vol. 192(1), pages 343-347, January.
    4. Jaber, Mohamad Y. & Bonney, Maurice, 1999. "The economic manufacture/order quantity (EMQ/EOQ) and the learning curve: Past, present, and future," International Journal of Production Economics, Elsevier, vol. 59(1-3), pages 93-102, March.
    5. Koulamas, Christos & Kyparisis, George J., 2007. "Single-machine and two-machine flowshop scheduling with general learning functions," European Journal of Operational Research, Elsevier, vol. 178(2), pages 402-407, April.
    6. Biskup, Dirk, 1999. "Single-machine scheduling with learning considerations," European Journal of Operational Research, Elsevier, vol. 115(1), pages 173-178, May.
    7. G Mosheiov, 2001. "Parallel machine scheduling with a learning effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(10), pages 1165-1169, October.
    8. Biskup, Dirk, 2008. "A state-of-the-art review on scheduling with learning effects," European Journal of Operational Research, Elsevier, vol. 188(2), pages 315-329, July.
    9. Kuo, Wen-Hung & Yang, Dar-Li, 2006. "Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1184-1190, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Annear, Luis Mauricio & Akhavan-Tabatabaei, Raha & Schmid, Verena, 2023. "Dynamic assignment of a multi-skilled workforce in job shops: An approximate dynamic programming approach," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1109-1125.
    2. Derya Deliktaş, 2022. "Self-adaptive memetic algorithms for multi-objective single machine learning-effect scheduling problems with release times," Flexible Services and Manufacturing Journal, Springer, vol. 34(3), pages 748-784, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Heuser, Patricia & Tauer, Björn, 2023. "Single-machine scheduling with product category-based learning and forgetting effects," Omega, Elsevier, vol. 115(C).
    2. Ji-Bo Wang & Ming-Zheng Wang, 2011. "Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects," Annals of Operations Research, Springer, vol. 191(1), pages 155-169, November.
    3. Wen-Hung Wu & Yunqiang Yin & T C E Cheng & Win-Chin Lin & Juei-Chao Chen & Shin-Yi Luo & Chin-Chia Wu, 2017. "A combined approach for two-agent scheduling with sum-of-processing-times-based learning effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(2), pages 111-120, February.
    4. Corominas, Albert & Olivella, Jordi & Pastor, Rafael, 2010. "A model for the assignment of a set of tasks when work performance depends on experience of all tasks involved," International Journal of Production Economics, Elsevier, vol. 126(2), pages 335-340, August.
    5. Wen-Hung Kuo, 2012. "Single-machine group scheduling with time-dependent learning effect and position-based setup time learning effect," Annals of Operations Research, Springer, vol. 196(1), pages 349-359, July.
    6. Bai, Danyu & Tang, Mengqian & Zhang, Zhi-Hai & Santibanez-Gonzalez, Ernesto DR, 2018. "Flow shop learning effect scheduling problem with release dates," Omega, Elsevier, vol. 78(C), pages 21-38.
    7. Radosław Rudek, 2012. "Scheduling problems with position dependent job processing times: computational complexity results," Annals of Operations Research, Springer, vol. 196(1), pages 491-516, July.
    8. Biskup, Dirk, 2008. "A state-of-the-art review on scheduling with learning effects," European Journal of Operational Research, Elsevier, vol. 188(2), pages 315-329, July.
    9. Kai-biao Sun & Hong-xing Li, 2009. "Some single-machine scheduling problems with actual time and position dependent learning effects," Fuzzy Information and Engineering, Springer, vol. 1(2), pages 161-177, June.
    10. Jiang, Zhongyi & Chen, Fangfang & Kang, Huiyan, 2013. "Single-machine scheduling problems with actual time-dependent and job-dependent learning effect," European Journal of Operational Research, Elsevier, vol. 227(1), pages 76-80.
    11. Lai, Peng-Jen & Lee, Wen-Chiung, 2011. "Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects," Omega, Elsevier, vol. 39(5), pages 467-471, October.
    12. Zhongyi Jiang & Fangfang Chen & Xiandong Zhang, 2017. "Single-machine scheduling with times-based and job-dependent learning effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(7), pages 809-815, July.
    13. Dar-Li Yang & Wen-Hung Kuo, 2009. "Single-machine scheduling with both deterioration and learning effects," Annals of Operations Research, Springer, vol. 172(1), pages 315-327, November.
    14. J-B Wang, 2010. "Single-machine scheduling with a sum-of-actual-processing-time-based learning effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(1), pages 172-177, January.
    15. Cheng, Bayi & Zhu, Huijun & Li, Kai & Li, Yongjun, 2019. "Optimization of batch operations with a truncated batch-position-based learning effect," Omega, Elsevier, vol. 85(C), pages 134-143.
    16. Wang, J.-B. & Ng, C.T. & Cheng, T.C.E. & Liu, L.L., 2008. "Single-machine scheduling with a time-dependent learning effect," International Journal of Production Economics, Elsevier, vol. 111(2), pages 802-811, February.
    17. Lee, Wen-Chiung & Wu, Chin-Chia & Hsu, Peng-Hsiang, 2010. "A single-machine learning effect scheduling problem with release times," Omega, Elsevier, vol. 38(1-2), pages 3-11, February.
    18. Li, Gang & Wang, Xiao-Yuan & Wang, Ji-Bo & Sun, Lin-Yan, 2013. "Worst case analysis of flow shop scheduling problems with a time-dependent learning effect," International Journal of Production Economics, Elsevier, vol. 142(1), pages 98-104.
    19. Koulamas, Christos & Gupta, Sushil & Kyparisis, George J., 2010. "A unified analysis for the single-machine scheduling problem with controllable and non-controllable variable job processing times," European Journal of Operational Research, Elsevier, vol. 205(2), pages 479-482, September.
    20. Lung-Yu Li & Jian-You Xu & Shuenn-Ren Cheng & Xingong Zhang & Win-Chin Lin & Jia-Cheng Lin & Zong-Lin Wu & Chin-Chia Wu, 2022. "A Genetic Hyper-Heuristic for an Order Scheduling Problem with Two Scenario-Dependent Parameters in a Parallel-Machine Environment," Mathematics, MDPI, vol. 10(21), pages 1-22, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:68:y:2017:i:4:d:10.1007_s10898-017-0509-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.