IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v22y2019i5d10.1007_s10951-019-00605-x.html
   My bibliography  Save this article

A unified view of parallel machine scheduling with interdependent processing rates

Author

Listed:
  • Bahram Alidaee

    (The University of Mississippi)

  • Haibo Wang

    (Texas A&M International University)

  • R. Bryan Kethley

    (Middle Tennessee State University)

  • Frank Landram

    (West Texas A&M University)

Abstract

In this paper, we are concerned with the problem of scheduling n jobs on m machines. The job processing rate is interdependent and the jobs are non-preemptive. During the last several decades, a number of related models for parallel machine scheduling with interdependent processing rates (PMS-IPR) have appeared in the scheduling literature. Some of these models have been studied independently from one another. The purpose of this paper is to present two general PMS-IPR models that capture the essence of many of these existing PMS-IPR models. Several new complexity results are presented. We discuss improvements on some existing models. Furthermore, for an extension of the two related PMS-IPR models where they include many resource constraint models with controllable processing times, we propose an efficient dynamic programming procedure that solves the problem to optimality.

Suggested Citation

  • Bahram Alidaee & Haibo Wang & R. Bryan Kethley & Frank Landram, 2019. "A unified view of parallel machine scheduling with interdependent processing rates," Journal of Scheduling, Springer, vol. 22(5), pages 499-515, October.
    • Handle: RePEc:spr:jsched:v:22:y:2019:i:5:d:10.1007_s10951-019-00605-x
    DOI: 10.1007/s10951-019-00605-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-019-00605-x
    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/s10951-019-00605-x?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. Reddy Dondeti, V. & Mohanty, Bidhu B., 1998. "Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs," European Journal of Operational Research, Elsevier, vol. 105(3), pages 509-524, March.
    2. Lai, Peng-Jen & Lee, Wen-Chiung, 2011. "Single-machine scheduling with general sum-of-processing-time-based and position-based learning effects," Omega, Elsevier, vol. 39(5), pages 467-471, October.
    3. Fündeling, C.-U. & Trautmann, N., 2010. "A priority-rule method for project scheduling with work-content constraints," European Journal of Operational Research, Elsevier, vol. 203(3), pages 568-574, June.
    4. Alidaee, Bahram & Ahmadian, Ahmad, 1993. "Two parallel machine sequencing problems involving controllable job processing times," European Journal of Operational Research, Elsevier, vol. 70(3), pages 335-341, November.
    5. Shabtay, Dvir & Kaspi, Moshe, 2006. "Parallel machine scheduling with a convex resource consumption function," European Journal of Operational Research, Elsevier, vol. 173(1), pages 92-107, August.
    6. I. Meilijson & A. Tamir, 1984. "Minimizing Flow Time on Parallel Identical Processors with Variable Unit Processing Time," Operations Research, INFORMS, vol. 32(2), pages 440-448, April.
    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. E. L. Lawler & C. U. Martel, 1989. "Preemptive Scheduling of Two Uniform Machines to Minimize the Number of Late Jobs," Operations Research, INFORMS, vol. 37(2), pages 314-318, April.
    9. 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.
    10. Amaddeo, H. F. & Nawijn, W. M. & van Harten, A., 1997. "One-machine job-scheduling with non-constant capacity -- Minimizing weighted completion times," European Journal of Operational Research, Elsevier, vol. 102(3), pages 502-512, November.
    11. Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.
    12. Weglarz, Jan & Józefowska, Joanna & Mika, Marek & Waligóra, Grzegorz, 2011. "Project scheduling with finite or infinite number of activity processing modes - A survey," European Journal of Operational Research, Elsevier, vol. 208(3), pages 177-205, February.
    13. E. L. Lawler & B. D. Sivazlian, 1978. "Minimization of Time-Varying Costs in Single-Machine Scheduling," Operations Research, INFORMS, vol. 26(4), pages 563-569, August.
    14. Allahverdi, Ali & Gupta, Jatinder N. D. & Aldowaisan, Tariq, 1999. "A review of scheduling research involving setup considerations," Omega, Elsevier, vol. 27(2), pages 219-239, April.
    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. 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.
    17. Moshe Dror & Helman I. Stern & Jan Karel Lenstra, 1987. "Parallel Machine Scheduling: Processing Rates Dependent on Number of Jobs in Operation," Management Science, INFORMS, vol. 33(8), pages 1001-1009, August.
    18. 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.
    19. Kenneth R. Baker & Henry L. W. Nuttle, 1980. "Sequencing independent jobs with a single resource," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 27(3), pages 499-510, September.
    20. Lin, Jun & Qian, Yanjun & Cui, Wentian & Goh, Thong Ngee, 2015. "An effective approach for scheduling coupled activities in development projects," European Journal of Operational Research, Elsevier, vol. 243(1), pages 97-108.
    21. Zhi-Long Chen & Nicholas G. Hall, 2008. "Maximum Profit Scheduling," Manufacturing & Service Operations Management, INFORMS, vol. 10(1), pages 84-107, February.
    22. D. K. Friesen & B. L. Deuermeyer, 1981. "Analysis of Greedy Solutions for a Replacement Part Sequencing Problem," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 74-87, February.
    23. H. C. Huang, 1986. "On Minimizing Flow Time on Processors with Variable Unit Processing Time," Operations Research, INFORMS, vol. 34(5), pages 801-802, October.
    24. Gorczyca, Mateusz & Janiak, Adam, 2010. "Resource level minimization in the discrete-continuous scheduling," European Journal of Operational Research, Elsevier, vol. 203(1), pages 32-41, May.
    25. Liao, Ching-Jong & Lin, Chien-Hung, 2003. "Makespan minimization for two uniform parallel machines," International Journal of Production Economics, Elsevier, vol. 84(2), pages 205-213, May.
    26. Bahram Alidaee & Gary A. Kochenberger, 2005. "A Note on a Simple Dynamic Programming Approach to the Single-Sink, Fixed-Charge Transportation Problem," Transportation Science, INFORMS, vol. 39(1), pages 140-143, February.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. 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.
    3. Yang, Wen-Hua & Chand, Suresh, 2008. "Learning and forgetting effects on a group scheduling problem," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1033-1044, June.
    4. 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.
    5. 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.
    6. Heuser, Patricia & Tauer, Björn, 2023. "Single-machine scheduling with product category-based learning and forgetting effects," Omega, Elsevier, vol. 115(C).
    7. 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.
    8. 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.
    9. Cheng, T.C.E. & Shafransky, Y. & Ng, C.T., 2016. "An alternative approach for proving the NP-hardness of optimization problems," European Journal of Operational Research, Elsevier, vol. 248(1), pages 52-58.
    10. 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.
    11. 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.
    12. Al-Anzi, Fawaz S. & Allahverdi, Ali & Kovalyov, Mikhail Y., 2007. "Batching deteriorating items with applications in computer communication and reverse logistics," European Journal of Operational Research, Elsevier, vol. 182(3), pages 1002-1011, November.
    13. 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.
    14. W-H Kuo & D-L Yang, 2011. "A note on due-date assignment and single-machine scheduling with deteriorating jobs and learning effects," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(1), pages 206-210, January.
    15. 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.
    16. Min Ji & Chou-Jung Hsu & Dar-Li Yang, 2013. "Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration," Journal of Combinatorial Optimization, Springer, vol. 26(3), pages 437-447, October.
    17. Li, Shisheng & Ng, C.T. & Cheng, T.C.E. & Yuan, Jinjiang, 2011. "Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 210(3), pages 482-488, May.
    18. 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.
    19. 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.
    20. Wang, Ji-Bo, 2007. "Single-machine scheduling problems with the effects of learning and deterioration," Omega, Elsevier, vol. 35(4), pages 397-402, August.

    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:jsched:v:22:y:2019:i:5:d:10.1007_s10951-019-00605-x. 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.