IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v186y2017icp1-7.html
   My bibliography  Save this article

Parallel-machine scheduling with machine-dependent maintenance periodic recycles

Author

Listed:
  • Li, Guo
  • Liu, Mengqi
  • Sethi, Suresh P.
  • Xu, Dehua

Abstract

Parallel machine structure is very common in modern production systems. Its performance sometimes has a decisive impact on the whole productivity. In this paper, we consider a parallel-machine scheduling problem where each machine is subject to periodic maintenance. Instead of assuming all the machines have the same maintenance periodic cycle, we assume the maintenance periodic cycles are machine-dependent. The objective is to schedule all the jobs to the machines such that the makespan is minimized. We first provide computational complexity and non-approximability analyses of the problem and then present two mathematical programming models to tackle small-sized instances. Thereafter, we present a worst-case analysis of the classical LPT and LS algorithms for the problem. Then we propose two improved heuristic algorithms based on some observations of large-sized instances. In order to evaluate the performance of the heuristic algorithms, we resort to a lower bound of the optimal makespan, and find that it has a very interesting characteristic. Numerical experiments show that the improved heuristic algorithm MLPT improves the objective value of the LPT schedule by about 6.75% on average and that the MLPT heuristic algorithm has an average-case relative error less than 1.57% for all combinations of instances, which means that it is very suitable for real world applications.

Suggested Citation

  • Li, Guo & Liu, Mengqi & Sethi, Suresh P. & Xu, Dehua, 2017. "Parallel-machine scheduling with machine-dependent maintenance periodic recycles," International Journal of Production Economics, Elsevier, vol. 186(C), pages 1-7.
    • Handle: RePEc:eee:proeco:v:186:y:2017:i:c:p:1-7
    DOI: 10.1016/j.ijpe.2017.01.014
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527317300142
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ijpe.2017.01.014?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. 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.
    2. 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.
    3. Sun, Kaibiao & Li, Hongxing, 2010. "Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines," International Journal of Production Economics, Elsevier, vol. 124(1), pages 151-158, March.
    4. Yin, Yunqiang & Cheng, T.C.E. & Wang, Du-Juan, 2016. "Rescheduling on identical parallel machines with machine disruptions to minimize total completion time," European Journal of Operational Research, Elsevier, vol. 252(3), pages 737-749.
    5. Wang, Xiuli & Cheng, T.C.E., 2015. "A heuristic for scheduling jobs on two identical parallel machines with a machine availability constraint," International Journal of Production Economics, Elsevier, vol. 161(C), pages 74-82.
    6. Ma, Ran & Yuan, Jinjiang, 2014. "Online tradeoff scheduling on a single machine to minimize makespan and total weighted completion time," International Journal of Production Economics, Elsevier, vol. 158(C), pages 114-119.
    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. Li, Guo & Li, Na & Sambandam, Narayanasamy & Sethi, Suresh P. & Zhang, Faping, 2018. "Flow shop scheduling with jobs arriving at different times," International Journal of Production Economics, Elsevier, vol. 206(C), pages 250-260.
    2. Song Jiu, 2021. "A two-phase approach for integrating preventive maintenance with production and delivery in an unreliable coal mine," Journal of Heuristics, Springer, vol. 27(6), pages 991-1020, December.
    3. Shastitko, Anastasia (Шаститко, Анастасия), 2018. "Application of the Conclusions of the Behavioral Economy to the Behavior of Civil Servants: Methodological Aspects [Применение Выводов Поведенческой Экономики К Поведению Государственных Служащих: ," Working Papers 031823, Russian Presidential Academy of National Economy and Public Administration.
    4. Hanane Krim & Nicolas Zufferey & Jean-Yves Potvin & Rachid Benmansour & David Duvivier, 2022. "Tabu search for a parallel-machine scheduling problem with periodic maintenance, job rejection and weighted sum of completion times," Journal of Scheduling, Springer, vol. 25(1), pages 89-105, February.
    5. Nasini, Stefano & Nessah, Rabia, 2022. "A multi-machine scheduling solution for homogeneous processing: Asymptotic approximation and applications," International Journal of Production Economics, Elsevier, vol. 251(C).
    6. Wieslaw Kubiak & Yanling Feng & Guo Li & Suresh P. Sethi & Chelliah Sriskandarajah, 2020. "Efficient algorithms for flexible job shop scheduling with parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(4), pages 272-288, June.
    7. Hanane Krim & Rachid Benmansour & David Duvivier & Daoud Aït-Kadi & Said Hanafi, 2020. "Heuristics for the single machine weighted sum of completion times scheduling problem with periodic maintenance," Computational Optimization and Applications, Springer, vol. 75(1), pages 291-320, January.
    8. Feng, Yanling & Li, Guo & Sethi, Suresh P., 2018. "A three-layer chromosome genetic algorithm for multi-cell scheduling with flexible routes and machine sharing," International Journal of Production Economics, Elsevier, vol. 196(C), pages 269-283.
    9. Feng, Hanxin & Xi, Lifeng & Xiao, Lei & Xia, Tangbin & Pan, Ershun, 2018. "Imperfect preventive maintenance optimization for flexible flowshop manufacturing cells considering sequence-dependent group scheduling," Reliability Engineering and System Safety, Elsevier, vol. 176(C), pages 218-229.

    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. Boccia, Maurizio & Masone, Adriano & Sterle, Claudio & Murino, Teresa, 2023. "The parallel AGV scheduling problem with battery constraints: A new formulation and a matheuristic approach," European Journal of Operational Research, Elsevier, vol. 307(2), pages 590-603.
    2. Xia, Tangbin & Jin, Xiaoning & Xi, Lifeng & Ni, Jun, 2015. "Production-driven opportunistic maintenance for batch production based on MAM–APB scheduling," European Journal of Operational Research, Elsevier, vol. 240(3), pages 781-790.
    3. Wu, Xueqi & Che, Ada, 2019. "A memetic differential evolution algorithm for energy-efficient parallel machine scheduling," Omega, Elsevier, vol. 82(C), pages 155-165.
    4. 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.
    5. 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.
    6. Yunqiang Yin & Jianyou Xu & T. C. E. Cheng & Chin‐Chia Wu & Du‐Juan Wang, 2016. "Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(2), pages 172-183, March.
    7. Sandeep Kumar & Bhupesh Kumar Lad, 2017. "Integrated production and maintenance planning for parallel machine system considering cost of rejection," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(7), pages 834-846, July.
    8. Seyed Habib A. Rahmati & Abbas Ahmadi & Kannan Govindan, 2018. "A novel integrated condition-based maintenance and stochastic flexible job shop scheduling problem: simulation-based optimization approach," Annals of Operations Research, Springer, vol. 269(1), pages 583-621, October.
    9. Tan, Zhiyi & Chen, Yong & Zhang, An, 2013. "On the exact bounds of SPT for scheduling on parallel machines with availability constraints," International Journal of Production Economics, Elsevier, vol. 146(1), pages 293-299.
    10. Luo, Wenchang & Liu, Feng, 2017. "On single-machine scheduling with workload-dependent maintenance duration," Omega, Elsevier, vol. 68(C), pages 119-122.
    11. Hanane Krim & Nicolas Zufferey & Jean-Yves Potvin & Rachid Benmansour & David Duvivier, 2022. "Tabu search for a parallel-machine scheduling problem with periodic maintenance, job rejection and weighted sum of completion times," Journal of Scheduling, Springer, vol. 25(1), pages 89-105, February.
    12. Tangbin Xia & Xiangxin An & Huaqiang Yang & Yimin Jiang & Yuhui Xu & Meimei Zheng & Ershun Pan, 2023. "Efficient Energy Use in Manufacturing Systems—Modeling, Assessment, and Management Strategy," Energies, MDPI, vol. 16(3), pages 1-20, January.
    13. Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.
    14. 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.
    15. Shijin Wang & Ming Liu, 2016. "Two-machine flow shop scheduling integrated with preventive maintenance planning," International Journal of Systems Science, Taylor & Francis Journals, vol. 47(3), pages 672-690, February.
    16. 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.
    17. Wenchang Luo & Rylan Chin & Alexander Cai & Guohui Lin & Bing Su & An Zhang, 2022. "A tardiness-augmented approximation scheme for rejection-allowed multiprocessor rescheduling," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 690-722, August.
    18. Berthaut, F. & Gharbi, A. & Dhouib, K., 2011. "Joint modified block replacement and production/inventory control policy for a failure-prone manufacturing cell," Omega, Elsevier, vol. 39(6), pages 642-654, December.
    19. 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.
    20. Tambe, Pravin P. & Kulkarni, Makarand S., 2022. "A reliability based integrated model of maintenance planning with quality control and production decision for improving operational performance," Reliability Engineering and System Safety, Elsevier, vol. 226(C).

    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:proeco:v:186:y:2017:i:c:p:1-7. 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/locate/ijpe .

    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.