IDEAS home Printed from https://ideas.repec.org/a/taf/tprsxx/v54y2016i12p3475-3490.html
   My bibliography  Save this article

Due-window assignment and scheduling with general position-dependent processing times involving a deteriorating and compressible maintenance activity

Author

Listed:
  • Hui Zhu
  • Min Li
  • Zhangjin Zhou
  • Yun You

Abstract

In this paper, we consider common due-window assignment and scheduling problems with general position-dependent processing times involving deteriorating and compressible maintenance activity on a single machine. Two models associated with maintenance activity are examined in this article, in which the maintenance length is assumed to be either time-dependent and compressible or position-dependent and compressible. The objective is to find jointly the location and size of due-window, position of maintenance as well as resource amount allocated to it, and job sequence to minimise a total cost function based on earliness, tardiness, window location, window size and resource cost. We show that the problem considered in each of the two models’ setting can be optimally solved with polynomial time algorithm by reducing to assignment problem. Finally, two examples are provided to illustrate the solution procedures.

Suggested Citation

  • 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.
    • Handle: RePEc:taf:tprsxx:v:54:y:2016:i:12:p:3475-3490
    DOI: 10.1080/00207543.2015.1067379
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1080/00207543.2015.1067379
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1080/00207543.2015.1067379?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. Yin, Yunqiang & Cheng, T.C.E. & Hsu, Chou-Jung & Wu, Chin-Chia, 2013. "Single-machine batch delivery scheduling with an assignable common due window," Omega, Elsevier, vol. 41(2), pages 216-225.
    2. 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.
    3. Gordon, Valery & Proth, Jean-Marie & Chu, Chengbin, 2002. "A survey of the state-of-the-art of common due date assignment and scheduling research," European Journal of Operational Research, Elsevier, vol. 139(1), pages 1-25, May.
    4. G Mosheiov & A Sarig, 2008. "A due-window assignment problem with position-dependent processing times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(7), pages 997-1003, July.
    5. S. S. Panwalkar & M. L. Smith & A. Seidmann, 1982. "Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem," Operations Research, INFORMS, vol. 30(2), pages 391-399, April.
    6. Su, Ling-Huey & Lien, Chun-Yuan, 2009. "Scheduling parallel machines with resource-dependent processing times," International Journal of Production Economics, Elsevier, vol. 117(2), pages 256-266, February.
    7. 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.
    8. Yang, Dar-Li & Lai, Chien-Jung & Yang, Suh-Jenq, 2014. "Scheduling problems with multiple due windows assignment and controllable processing times on a single machine," International Journal of Production Economics, Elsevier, vol. 150(C), pages 96-103.
    9. Liman, Surya D. & Panwalkar, Shrikant S. & Thongmee, Sansern, 1996. "Determination of common due window location in a single machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 93(1), pages 68-74, August.
    10. 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.
    11. B Alidaee & N K Womer, 1999. "Scheduling with time dependent processing times: Review and extensions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(7), pages 711-720, July.
    12. Cheng, T.C.E. & Yang, Suh-Jenq & Yang, Dar-Li, 2012. "Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity," International Journal of Production Economics, Elsevier, vol. 135(1), pages 154-161.
    13. Yeung, W. K. & Oguz, Ceyda & Edwin Cheng, T. C., 2004. "Two-stage flowshop earliness and tardiness machine scheduling involving a common due window," International Journal of Production Economics, Elsevier, vol. 90(3), pages 421-434, August.
    14. Lee, Chung-Yee & Lin, Chen-Sin, 2001. "Single-machine scheduling with maintenance and repair rate-modifying activities," European Journal of Operational Research, Elsevier, vol. 135(3), pages 493-513, December.
    15. R. G. Vickson, 1980. "Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine," Operations Research, INFORMS, vol. 28(5), pages 1155-1167, October.
    16. 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.
    17. 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.
    18. 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.
    19. 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.
    20. Yong He & Min Ji & T. C. E. Cheng, 2005. "Single machine scheduling with a restricted rate‐modifying activity," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(4), pages 361-369, June.
    21. 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.
    22. Cheng, T. C. E. & Gupta, M. C., 1989. "Survey of scheduling research involving due date determination decisions," European Journal of Operational Research, Elsevier, vol. 38(2), pages 156-166, January.
    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. Xia, Tangbin & Dong, Yifan & Xiao, Lei & Du, Shichang & Pan, Ershun & Xi, Lifeng, 2018. "Recent advances in prognostics and health management for advanced manufacturing paradigms," Reliability Engineering and System Safety, Elsevier, vol. 178(C), pages 255-268.
    2. Baruch Mor, 2019. "Minmax scheduling problems with common due-date and completion time penalty," Journal of Combinatorial Optimization, Springer, vol. 38(1), pages 50-71, July.

    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. 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.
    2. 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.
    3. Min Ji & Xin Zhang & Xiaoying Tang & T.C.E. Cheng & Guiyi Wei & Yuanyuan Tan, 2016. "Group scheduling with group-dependent multiple due windows assignment," International Journal of Production Research, Taylor & Francis Journals, vol. 54(4), pages 1244-1256, February.
    4. 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.
    5. 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.
    6. 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.
    7. Zhusong Liu & Zhenyou Wang & Yuan-Yuan Lu, 2017. "A Bicriteria Approach for Single Machine Scheduling with Resource Allocation, Learning Effect and a Deteriorating Maintenance Activity," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(04), pages 1-16, August.
    8. Cheng, T.C.E. & Yang, Suh-Jenq & Yang, Dar-Li, 2012. "Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity," International Journal of Production Economics, Elsevier, vol. 135(1), pages 154-161.
    9. Chun-Lai Liu & Jian-Jun Wang, 2016. "Unrelated Parallel-Machine Scheduling with Controllable Processing Times and Impact of Deteriorating Maintenance Activities under Consideration," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(01), pages 1-16, February.
    10. Shi-Sheng Li & Ren-Xia Chen, 2017. "Scheduling with Rejection and a Deteriorating Maintenance Activity on a Single Machine," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(02), pages 1-17, April.
    11. Kim, Hyunjoon & Kim, Byung-In, 2022. "Optimal sequence for single server scheduling incorporating a rate-modifying activity under job-dependent linear deterioration," European Journal of Operational Research, Elsevier, vol. 298(2), pages 439-450.
    12. Yin, Yunqiang & Cheng, T.C.E. & Hsu, Chou-Jung & Wu, Chin-Chia, 2013. "Single-machine batch delivery scheduling with an assignable common due window," Omega, Elsevier, vol. 41(2), pages 216-225.
    13. 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.
    14. 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.
    15. Zhanguo Zhu & Feifeng Zheng & Chengbin Chu, 2017. "Multitasking scheduling problems with a rate-modifying activity," International Journal of Production Research, Taylor & Francis Journals, vol. 55(1), pages 296-312, January.
    16. Long Zhang & Yuzhong Zhang & Qingguo Bai, 0. "An approximation algorithm for a supply-chain scheduling problem with an assignable common due window and holding time," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-13.
    17. 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.
    18. Stanisław Gawiejnowicz, 2020. "A review of four decades of time-dependent scheduling: main results, new topics, and open problems," Journal of Scheduling, Springer, vol. 23(1), pages 3-47, February.
    19. Geurtsen, M. & Didden, Jeroen B.H.C. & Adan, J. & Atan, Z. & Adan, I., 2023. "Production, maintenance and resource scheduling: A review," European Journal of Operational Research, Elsevier, vol. 305(2), pages 501-529.
    20. 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.

    More about this item

    Statistics

    Access and download statistics

    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:taf:tprsxx:v:54:y:2016:i:12:p:3475-3490. 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: Chris Longhurst (email available below). General contact details of provider: http://www.tandfonline.com/TPRS20 .

    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.