IDEAS home Printed from https://ideas.repec.org/a/eee/apmaco/v250y2015icp628-635.html
   My bibliography  Save this article

Single-machine scheduling CON/SLK due window assignment problems with sum-of-processed times based learning effect

Author

Listed:
  • Xingong, Zhang
  • Yong, Wang

Abstract

This paper studies systems that can be modeled by single-machine scheduling problems with due date assignment. The actual job processing time is a function of the sum of the processing times of the jobs already processed. The due date assignment methods include the common due date (CON) and the slack due date (SLK). The problem is to determine optimal due date values that minimize objective functions which includes the cost of changing the due dates, a possible penalty for the total earliness of the scheduled jobs and the total penalty for discarding jobs. For the common due date and slack due date, we give polynomial-time dynamic programming algorithms to find the optimal jobs sequence, respectively.

Suggested Citation

  • Xingong, Zhang & Yong, Wang, 2015. "Single-machine scheduling CON/SLK due window assignment problems with sum-of-processed times based learning effect," Applied Mathematics and Computation, Elsevier, vol. 250(C), pages 628-635.
    • Handle: RePEc:eee:apmaco:v:250:y:2015:i:c:p:628-635
    DOI: 10.1016/j.amc.2014.11.011
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0096300314015173
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.amc.2014.11.011?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. 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.
    2. Li, Shisheng & Ng, C.T. & Yuan, Jinjiang, 2011. "Group scheduling and due date assignment on a single machine," International Journal of Production Economics, Elsevier, vol. 130(2), pages 230-235, April.
    3. Slotnick, Susan A. & Sobel, Matthew J., 2005. "Manufacturing lead-time rules: Customer retention versus tardiness costs," European Journal of Operational Research, Elsevier, vol. 163(3), pages 825-856, June.
    4. Shabtay, Dvir, 2010. "Scheduling and due date assignment to minimize earliness, tardiness, holding, due date assignment and batch delivery costs," International Journal of Production Economics, Elsevier, vol. 123(1), pages 235-242, January.
    5. Nicholas G. Hall & Chris N. Potts, 2003. "Supply chain scheduling: Batching and delivery," Operations Research, INFORMS, vol. 51(4), pages 566-584, August.
    6. Li, Shisheng & Ng, C.T. & Yuan, Jinjiang, 2011. "Scheduling deteriorating jobs with CON/SLK due date assignment on a single machine," International Journal of Production Economics, Elsevier, vol. 131(2), pages 747-751, June.
    7. Yu-Ping Niu & Long Wan & Ji-Bo Wang, 2015. "A Note on Scheduling Jobs with Extended Sum-of-Processing-Times-Based and Position-Based Learning Effect," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 32(02), pages 1-12.
    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. Azaron, Amir & Fynes, Brian & Modarres, Mohammad, 2011. "Due date assignment in repetitive projects," International Journal of Production Economics, Elsevier, vol. 129(1), pages 79-85, January.
    10. Gordon, Valery S. & Strusevich, Vitaly A., 2009. "Single machine scheduling and due date assignment with positionally dependent processing times," European Journal of Operational Research, Elsevier, vol. 198(1), pages 57-62, 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. 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. Li, Shisheng & Ng, C.T. & Yuan, Jinjiang, 2011. "Scheduling deteriorating jobs with CON/SLK due date assignment on a single machine," International Journal of Production Economics, Elsevier, vol. 131(2), pages 747-751, June.
    2. Su, Ling-Huey & Tien, Yi-Yu, 2011. "Minimizing mean absolute deviation of completion time about a common due window subject to maximum tardiness for a single machine," International Journal of Production Economics, Elsevier, vol. 134(1), pages 196-203, November.
    3. Shang-Chia Liu & Jiahui Duan & Win-Chin Lin & Wen-Hsiang Wu & Jan-Yee Kung & Hau Chen & Chin-Chia Wu, 2018. "A Branch-and-Bound Algorithm for Two-Agent Scheduling with Learning Effect and Late Work Criterion," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(05), pages 1-24, October.
    4. Koulamas, Christos & Kyparisis, George J., 2023. "A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems," European Journal of Operational Research, Elsevier, vol. 305(3), pages 999-1017.
    5. 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.
    6. 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.
    7. Du-Juan Wang & Yunqiang Yin & Shuenn-Ren Cheng & T.C.E. Cheng & Chin-Chia Wu, 2016. "Due date assignment and scheduling on a single machine with two competing agents," International Journal of Production Research, Taylor & Francis Journals, vol. 54(4), pages 1152-1169, February.
    8. Yunqiang Yin & Doudou Li & Dujuan Wang & T. C. E. Cheng, 2021. "Single-machine serial-batch delivery scheduling with two competing agents and due date assignment," Annals of Operations Research, Springer, vol. 298(1), pages 497-523, March.
    9. Slotnick, Susan A., 2011. "Order acceptance and scheduling: A taxonomy and review," European Journal of Operational Research, Elsevier, vol. 212(1), pages 1-11, July.
    10. Finke, Gerd & Gara-Ali, Ahmed & Espinouse, Marie-Laure & Jost, Vincent & Moncel, Julien, 2017. "Unified matrix approach to solve production-maintenance problems on a single machine," Omega, Elsevier, vol. 66(PA), pages 140-146.
    11. 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.
    12. Anna Arigliano & Gianpaolo Ghiani & Antonio Grieco & Emanuela Guerriero, 2017. "Single-machine time-dependent scheduling problems with fixed rate-modifying activities and resumable jobs," 4OR, Springer, vol. 15(2), pages 201-215, June.
    13. George Steiner & Rui Zhang, 2011. "Revised Delivery-Time Quotation in Scheduling with Tardiness Penalties," Operations Research, INFORMS, vol. 59(6), pages 1504-1511, December.
    14. Li, Shisheng & Ng, C.T. & Yuan, Jinjiang, 2011. "Group scheduling and due date assignment on a single machine," International Journal of Production Economics, Elsevier, vol. 130(2), pages 230-235, April.
    15. Janiak, Adam & Krysiak, Tomasz, 2012. "Scheduling jobs with values dependent on their completion times," International Journal of Production Economics, Elsevier, vol. 135(1), pages 231-241.
    16. 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.
    17. 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.
    18. 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.
    19. 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.
    20. Ying Chen & Xiaole Ma & Guiqing Zhang & Yongxi Cheng, 2023. "On optimal due date assignment without restriction and resource allocation in group technology scheduling," Journal of Combinatorial Optimization, Springer, vol. 45(2), pages 1-19, March.

    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:eee:apmaco:v:250:y:2015:i:c:p:628-635. 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: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    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.