IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v40y2012i6p791-804.html
   My bibliography  Save this article

Single machine scheduling with general positional deterioration and rate-modifying maintenance

Author

Listed:
  • Rustogi, Kabir
  • Strusevich, Vitaly A.

Abstract

We present polynomial-time algorithms for single machine problems with generalized positional deterioration effects and machine maintenance. The decisions should be taken regarding possible sequences of jobs and on the number of maintenance activities to be included into a schedule in order to minimize the overall makespan. We deal with general non-decreasing functions to represent deterioration rates of job processing times. Another novel extension of existing models is our assumption that a maintenance activity does not necessarily fully restore the machine to its original perfect state. In the resulting schedules, the jobs are split into groups, a particular group to be sequenced after a particular maintenance period, and the actual processing time of a job is affected by the group that job is placed into and its position within the group.

Suggested Citation

  • Rustogi, Kabir & Strusevich, Vitaly A., 2012. "Single machine scheduling with general positional deterioration and rate-modifying maintenance," Omega, Elsevier, vol. 40(6), pages 791-804.
    • Handle: RePEc:eee:jomega:v:40:y:2012:i:6:p:791-804
    DOI: 10.1016/j.omega.2011.12.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048311001794
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2011.12.007?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. Yang, Suh-Jenq & Yang, Dar-Li, 2010. "Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities," Omega, Elsevier, vol. 38(6), pages 528-533, December.
    2. Biskup, Dirk, 1999. "Single-machine scheduling with learning considerations," European Journal of Operational Research, Elsevier, vol. 115(1), pages 173-178, May.
    3. Mosheiov, Gur, 2001. "Scheduling problems with a learning effect," European Journal of Operational Research, Elsevier, vol. 132(3), pages 687-693, August.
    4. A Bachman & A Janiak, 2004. "Scheduling jobs with position-dependent processing times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(3), pages 257-264, March.
    5. Chen, Wen-Jinn, 2009. "Minimizing number of tardy jobs on a single machine subject to periodic maintenance," Omega, Elsevier, vol. 37(3), pages 591-599, June.
    6. G Mosheiov & J B Sidney, 2010. "Scheduling a deteriorating maintenance activity on a single machine," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(5), pages 882-887, May.
    7. Mosheiov, Gur & Sidney, Jeffrey B., 2003. "Scheduling with general job-dependent learning curves," European Journal of Operational Research, Elsevier, vol. 147(3), pages 665-670, June.
    8. W-H Kuo & D-L Yang, 2008. "Minimizing the makespan in a single-machine scheduling problem with the cyclic process of an aging effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(3), pages 416-420, March.
    9. 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.
    10. M. A. Kubzin & V. A. Strusevich, 2006. "Planning Machine Maintenance in Two-Machine Shop Scheduling," Operations Research, INFORMS, vol. 54(4), pages 789-800, August.
    11. 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.
    12. Lee, C. -Y. & Leon, V. J., 2001. "Machine scheduling with a rate-modifying activity," European Journal of Operational Research, Elsevier, vol. 128(1), pages 119-128, January.
    13. Chen, Jen-Shiang, 2008. "Optimization models for the tool change scheduling problem," Omega, Elsevier, vol. 36(5), pages 888-894, October.
    14. Lodree Jr., Emmett J. & Geiger, Christopher D., 2010. "A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration," European Journal of Operational Research, Elsevier, vol. 201(2), pages 644-648, March.
    15. 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.
    16. X Qi & T Chen & F Tu, 1999. "Scheduling the maintenance on a single machine," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(10), pages 1071-1078, October.
    17. Mohan Gopalakrishnan & Sanjay L. Ahire & David M. Miller, 1997. "Maximizing the Effectiveness of a Preventive Maintenance System: An Adaptive Modeling Approach," Management Science, INFORMS, vol. 43(6), pages 827-840, June.
    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. Du-Juan Wang & Yunqiang Yin & Mengqi Liu, 2016. "Bicriteria scheduling problems involving job rejection, controllable processing times and rate-modifying activity," International Journal of Production Research, Taylor & Francis Journals, vol. 54(12), pages 3691-3705, June.
    2. Norelhouda Sekkal & Fayçal Belkaid, 2020. "A multi-objective simulated annealing to solve an identical parallel machine scheduling problem with deterioration effect and resources consumption constraints," Journal of Combinatorial Optimization, Springer, vol. 40(3), pages 660-696, October.
    3. Yang, Lixing & Zhou, Xuesong & Gao, Ziyou, 2014. "Credibility-based rescheduling model in a double-track railway network: a fuzzy reliable optimization approach," Omega, Elsevier, vol. 48(C), pages 75-93.
    4. Gawiejnowicz, Stanisław & Kurc, Wiesław, 2015. "Structural properties of time-dependent scheduling problems with the lp norm objective," Omega, Elsevier, vol. 57(PB), pages 196-202.
    5. Xu, Dehua & Wan, Long & Liu, Aihua & Yang, Dar-Li, 2015. "Single machine total completion time scheduling problem with workload-dependent maintenance duration," Omega, Elsevier, vol. 52(C), pages 101-106.
    6. Norelhouda Sekkal & Fayçal Belkaid, 0. "A multi-objective simulated annealing to solve an identical parallel machine scheduling problem with deterioration effect and resources consumption constraints," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-37.
    7. Ma, Ran & Tao, Jiping & Yuan, Jinjiang, 2016. "Online scheduling with linear deteriorating jobs to minimize the total weighted completion time," Applied Mathematics and Computation, Elsevier, vol. 273(C), pages 570-583.
    8. Gur Mosheiov & Daniel Oron, 2020. "Scheduling problems with a weight-modifying-activity," Annals of Operations Research, Springer, vol. 295(2), pages 737-745, December.
    9. Liliana Grigoriu & Dirk Briskorn, 2017. "Scheduling jobs and maintenance activities subject to job-dependent machine deteriorations," Journal of Scheduling, Springer, vol. 20(2), pages 183-197, April.
    10. Kabir Rustogi & Vitaly A. Strusevich, 2013. "Parallel Machine Scheduling: Impact of Adding Extra Machines," Operations Research, INFORMS, vol. 61(5), pages 1243-1257, October.
    11. Wang, Dujuan & Yin, Yunqiang & Cheng, T.C.E., 2018. "Parallel-machine rescheduling with job unavailability and rejection," Omega, Elsevier, vol. 81(C), pages 246-260.
    12. Yin, Yunqiang & Wang, Yan & Cheng, T.C.E. & Liu, Wenqi & Li, Jinhai, 2017. "Parallel-machine scheduling of deteriorating jobs with potential machine disruptions," Omega, Elsevier, vol. 69(C), pages 17-28.
    13. 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.
    14. Kabir Rustogi & Vitaly A. Strusevich, 2017. "Single machine scheduling with a generalized job-dependent cumulative effect," Journal of Scheduling, Springer, vol. 20(6), pages 583-592, December.
    15. Gara-Ali, Ahmed & Finke, Gerd & Espinouse, Marie-Laure, 2016. "Parallel-machine scheduling with maintenance: Praising the assignment problem," European Journal of Operational Research, Elsevier, vol. 252(1), pages 90-97.
    16. 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.
    17. Rustogi, Kabir & Strusevich, Vitaly A., 2012. "Simple matching vs linear assignment in scheduling models with positional effects: A critical review," European Journal of Operational Research, Elsevier, vol. 222(3), pages 393-407.
    18. Alan J. Soper & Vitaly A. Strusevich, 2020. "Refined conditions for V-shaped optimal sequencing on a single machine to minimize total completion time under combined effects," Journal of Scheduling, Springer, vol. 23(6), pages 665-680, December.

    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. Rustogi, Kabir & Strusevich, Vitaly A., 2012. "Simple matching vs linear assignment in scheduling models with positional effects: A critical review," European Journal of Operational Research, Elsevier, vol. 222(3), pages 393-407.
    2. Yang, Suh-Jenq & Yang, Dar-Li, 2010. "Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities," Omega, Elsevier, vol. 38(6), pages 528-533, December.
    3. 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.
    4. Hui Zhu & Min Li & Zhangjin Zhou & Yun You, 2016. "Due-window assignment and scheduling with general position-dependent processing times involving a deteriorating and compressible maintenance activity," International Journal of Production Research, Taylor & Francis Journals, vol. 54(12), pages 3475-3490, June.
    5. 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.
    6. Gara-Ali, Ahmed & Finke, Gerd & Espinouse, Marie-Laure, 2016. "Parallel-machine scheduling with maintenance: Praising the assignment problem," European Journal of Operational Research, Elsevier, vol. 252(1), pages 90-97.
    7. 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.
    8. 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.
    9. Janiak, Adam & Rudek, RadosLaw, 2010. "A note on a makespan minimization problem with a multi-ability learning effect," Omega, Elsevier, vol. 38(3-4), pages 213-217, June.
    10. J-J Wang & J-B Wang & F Liu, 2011. "Parallel machines scheduling with a deteriorating maintenance activity," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(10), pages 1898-1902, October.
    11. Maciej Drozdowski & Florian Jaehn & Radosław Paszkowski, 2017. "Scheduling Position-Dependent Maintenance Operations," Operations Research, INFORMS, vol. 65(6), pages 1657-1677, December.
    12. Wang, Ji-Bo, 2007. "Single-machine scheduling problems with the effects of learning and deterioration," Omega, Elsevier, vol. 35(4), pages 397-402, August.
    13. Shang-Chia Liu, 2015. "Common Due-Window Assignment and Group Scheduling with Position-Dependent Processing Times," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 32(06), pages 1-19, December.
    14. Janiak, Adam & Janiak, Władysław A. & Krysiak, Tomasz & Kwiatkowski, Tomasz, 2015. "A survey on scheduling problems with due windows," European Journal of Operational Research, Elsevier, vol. 242(2), pages 347-357.
    15. 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.
    16. Qian, Jin & Lin, Hexiang & Kong, Yufeng & Wang, Yuansong, 2020. "Tri-criteria single machine scheduling model with release times and learning factor," Applied Mathematics and Computation, Elsevier, vol. 387(C).
    17. 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.
    18. J-B Wang & Z-Q Xia, 2005. "Flow-shop scheduling with a learning effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(11), pages 1325-1330, November.
    19. 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.
    20. Zhang Xingong & Wang Yong & Bai Shikun, 2016. "Single-machine group scheduling problems with deteriorating and learning effect," International Journal of Systems Science, Taylor & Francis Journals, vol. 47(10), pages 2402-2410, July.

    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:jomega:v:40:y:2012:i:6:p:791-804. 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: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    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.