IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v298y2021i1d10.1007_s10479-020-03555-2.html
   My bibliography  Save this article

Parallel-machine serial-batching scheduling with release times under the effects of position-dependent learning and time-dependent deterioration

Author

Listed:
  • Jun Pei

    (Hefei University of Technology
    Key Laboratory of Process Optimization and Intelligent Decision-making of Ministry of Education)

  • Qingru Song

    (Hefei University of Technology
    Key Laboratory of Process Optimization and Intelligent Decision-making of Ministry of Education)

  • Baoyu Liao

    (Hefei University of Technology
    Key Laboratory of Process Optimization and Intelligent Decision-making of Ministry of Education)

  • Xinbao Liu

    (Hefei University of Technology
    Key Laboratory of Process Optimization and Intelligent Decision-making of Ministry of Education)

  • Panos M. Pardalos

    (University of Florida)

Abstract

This paper addresses a serial-batching scheduling problem where the jobs with arbitrary release times are scheduled on parallel machines with the objective to minimize the makespan. The effects of learning and deterioration are considered simultaneously, and each job’s actual processing time depends on the sum of previous jobs’ processing times and the position of the current job. Each machine can process up to $$ c $$ c jobs in the manner of serial batch, i.e., one after another with a setup time for each batch. Structural properties are identified for the special cases of the studied problem. Based on these derived structural properties, we propose a novel hybrid SC-VNS algorithm to solve the studied problem, which combines Society and Civilization (SC) algorithm with Variable Neighborhood Search (VNS). Computational experiments are conducted to evaluate the performance of the proposed hybrid algorithm and some other well-known algorithms. The results demonstrate that the proposed hybrid SC-VNS algorithm performs quite better than the compared algorithms in terms of the solution quality and the required running time.

Suggested Citation

  • Jun Pei & Qingru Song & Baoyu Liao & Xinbao Liu & Panos M. Pardalos, 2021. "Parallel-machine serial-batching scheduling with release times under the effects of position-dependent learning and time-dependent deterioration," Annals of Operations Research, Springer, vol. 298(1), pages 407-444, March.
    • Handle: RePEc:spr:annopr:v:298:y:2021:i:1:d:10.1007_s10479-020-03555-2
    DOI: 10.1007/s10479-020-03555-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-020-03555-2
    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/s10479-020-03555-2?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. Jun Pei & Bayi Cheng & Xinbao Liu & Panos M. Pardalos & Min Kong, 2019. "Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time," Annals of Operations Research, Springer, vol. 272(1), pages 217-241, January.
    2. Jun Pei & Xinbao Liu & Panos M. Pardalos & Athanasios Migdalas & Shanlin Yang, 2017. "Serial-batching scheduling with time-dependent setup time and effects of deterioration and learning on a single-machine," Journal of Global Optimization, Springer, vol. 67(1), pages 251-262, January.
    3. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.
    4. Wenjuan Fan & Jun Pei & Xinbao Liu & Panos M. Pardalos & Min Kong, 2018. "Serial-batching group scheduling with release times and the combined effects of deterioration and truncated job-dependent learning," Journal of Global Optimization, Springer, vol. 71(1), pages 147-163, May.
    5. Leung, Joseph Y.-T. & Ng, C.T. & Cheng, T.C. Edwin, 2008. "Minimizing sum of completion times for batch scheduling of jobs with deteriorating processing times," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1090-1099, June.
    6. Biskup, Dirk, 1999. "Single-machine scheduling with learning considerations," European Journal of Operational Research, Elsevier, vol. 115(1), pages 173-178, May.
    7. Sid Browne & Uri Yechiali, 1990. "Scheduling Deteriorating Jobs on a Single Processor," Operations Research, INFORMS, vol. 38(3), pages 495-498, June.
    8. Meng Li & Suresh P. Sethi & Jun Zhang, 2016. "Competing with bandit supply chains," Annals of Operations Research, Springer, vol. 240(2), pages 617-640, May.
    9. Wen-Chiung Lee, 2004. "A Note on Deteriorating Jobs and Learning in Single-Machine Scheduling Problems," International Journal of Business and Economics, School of Management Development, Feng Chia University, Taichung, Taiwan, vol. 3(1), pages 83-89, April.
    10. 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.
    11. Pei, Jun & Pardalos, Panos M. & Liu, Xinbao & Fan, Wenjuan & Yang, Shanlin, 2015. "Serial batching scheduling of deteriorating jobs in a two-stage supply chain to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 244(1), pages 13-25.
    12. Jun Pei & Xinbao Liu & Panos M. Pardalos & Wenjuan Fan & Shanlin Yang, 2017. "Scheduling deteriorating jobs on a single serial-batching machine with multiple job types and sequence-dependent setup times," Annals of Operations Research, Springer, vol. 249(1), pages 175-195, February.
    13. Yunpeng Pan & Zhe Liang, 2017. "Dual relaxations of the time-indexed ILP formulation for min–sum scheduling problems," Annals of Operations Research, Springer, vol. 249(1), pages 197-213, February.
    14. Anuj Kumar & Yinliang (Ricky) Tan, 2015. "The Demand Effects of Joint Product Advertising in Online Videos," Management Science, INFORMS, vol. 61(8), pages 1921-1937, August.
    15. Liang, Zhe & Feng, Yuan & Zhang, Xiaoning & Wu, Tao & Chaovalitwongse, Wanpracha Art, 2015. "Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 78(C), pages 238-259.
    16. Pei, Jun & Liu, Xinbao & Fan, Wenjuan & Pardalos, Panos M. & Lu, Shaojun, 2019. "A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers," Omega, Elsevier, vol. 82(C), pages 55-69.
    17. 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.
    18. Sundararaghavan, P. S. & Kunnathur, A. S., 1994. "Single machine scheduling with start time dependent processing times: Some solvable cases," European Journal of Operational Research, Elsevier, vol. 78(3), pages 394-403, November.
    19. Liao, Lu-Wen & Sheen, Gwo-Ji, 2008. "Parallel machine scheduling with machine availability and eligibility constraints," European Journal of Operational Research, Elsevier, vol. 184(2), pages 458-467, January.
    20. T.C. Edwin Cheng & Qing Ding & Mikhail Y. Kovalyov & Aleksander Bachman & Adam Janiak, 2003. "Scheduling jobs with piecewise linear decreasing processing times," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(6), pages 531-554, September.
    21. Xinbao Liu & Shaojun Lu & Jun Pei & Panos M. Pardalos, 2018. "A hybrid VNS-HS algorithm for a supply chain scheduling problem with deteriorating jobs," International Journal of Production Research, Taylor & Francis Journals, vol. 56(17), pages 5758-5775, September.
    22. T.C. Cheng & Guoqing Wang, 2000. "Single Machine Scheduling with Learning Effect Considerations," Annals of Operations Research, Springer, vol. 98(1), pages 273-290, December.
    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. Javad Rezaeian & Reza Alizadeh Foroutan & Toraj Mojibi & Yacob Khojasteh, 2023. "Sensitivity Analysis of the Unrelated Parallel Machine Scheduling Problem with Rework Processes and Machine Eligibility Restrictions," SN Operations Research Forum, Springer, vol. 4(3), pages 1-24, 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. Jun Pei & Bayi Cheng & Xinbao Liu & Panos M. Pardalos & Min Kong, 2019. "Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time," Annals of Operations Research, Springer, vol. 272(1), pages 217-241, January.
    2. Baoyu Liao & Qingru Song & Jun Pei & Shanlin Yang & Panos M. Pardalos, 2020. "Parallel-machine group scheduling with inclusive processing set restrictions, outsourcing option and serial-batching under the effect of step-deterioration," Journal of Global Optimization, Springer, vol. 78(4), pages 717-742, December.
    3. Jun Pei & Xinbao Liu & Panos M. Pardalos & Athanasios Migdalas & Shanlin Yang, 2017. "Serial-batching scheduling with time-dependent setup time and effects of deterioration and learning on a single-machine," Journal of Global Optimization, Springer, vol. 67(1), pages 251-262, January.
    4. Wang, Ji-Bo, 2007. "Single-machine scheduling problems with the effects of learning and deterioration," Omega, Elsevier, vol. 35(4), pages 397-402, August.
    5. Xingong Zhang & Guangle Yan & Wanzhen Huang & Guochun Tang, 2011. "Single-machine scheduling problems with time and position dependent processing times," Annals of Operations Research, Springer, vol. 186(1), pages 345-356, June.
    6. C. Ng & Q. Ding & T. Cheng & S. Lam, 2012. "Preemptive repayment policy for multiple loans," Annals of Operations Research, Springer, vol. 192(1), pages 141-150, January.
    7. Cheng, T. C. E. & Ding, Q. & Lin, B. M. T., 2004. "A concise survey of scheduling with time-dependent processing times," European Journal of Operational Research, Elsevier, vol. 152(1), pages 1-13, January.
    8. Pei, Jun & Liu, Xinbao & Fan, Wenjuan & Pardalos, Panos M. & Lu, Shaojun, 2019. "A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers," Omega, Elsevier, vol. 82(C), pages 55-69.
    9. Xue Huang & Na Yin & Wei-Wei Liu & Ji-Bo Wang, 2020. "Common Due Window Assignment Scheduling with Proportional Linear Deterioration Effects," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 37(01), pages 1-15, January.
    10. 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.
    11. Qian, Jianbo & Steiner, George, 2013. "Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine," European Journal of Operational Research, Elsevier, vol. 225(3), pages 547-551.
    12. Min Kong & Xinbao Liu & Jun Pei & Panos M. Pardalos & Nenad Mladenovic, 2020. "Parallel-batching scheduling with nonlinear processing times on a single and unrelated parallel machines," Journal of Global Optimization, Springer, vol. 78(4), pages 693-715, December.
    13. Zhang, Jun & Liu, Feng & Tang, Jiafu & Li, Yanhui, 2019. "The online integrated order picking and delivery considering Pickers’ learning effects for an O2O community supermarket," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 123(C), pages 180-199.
    14. 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.
    15. Cheng, Bayi & Leung, Joseph Y.-T. & Li, Kai & Yang, Shanlin, 2019. "Integrated optimization of material supplying, manufacturing, and product distribution: Models and fast algorithms," European Journal of Operational Research, Elsevier, vol. 277(1), pages 100-111.
    16. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    17. Xiaoyu Yu & Jingyi Qian & Yajing Zhang & Min Kong, 2023. "Supply Chain Scheduling Method for the Coordination of Agile Production and Port Delivery Operation," Mathematics, MDPI, vol. 11(15), pages 1-24, July.
    18. Peng Liu & Xiaoli Wang, 2017. "Maximum Lateness Scheduling on Two-Person Cooperative Games with Variable Processing Times and Common Due Date," Journal of Optimization, Hindawi, vol. 2017, pages 1-7, April.
    19. 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.
    20. Wenjuan Fan & Jun Pei & Xinbao Liu & Panos M. Pardalos & Min Kong, 2018. "Serial-batching group scheduling with release times and the combined effects of deterioration and truncated job-dependent learning," Journal of Global Optimization, Springer, vol. 71(1), pages 147-163, May.

    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:annopr:v:298:y:2021:i:1:d:10.1007_s10479-020-03555-2. 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.