IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v269y2018i2p621-632.html
   My bibliography  Save this article

Resource cost aware scheduling

Author

Listed:
  • Carrasco, Rodrigo A.
  • Iyengar, Garud
  • Stein, Cliff

Abstract

We are interested in the scheduling problem where there are several different resources that determine the speed at which a job runs and we pay depending on the amount of each resource that we use. This work is an extension of the resource dependent job processing time problem and the energy aware scheduling problems. We develop a new constant factor approximation algorithm for resource cost aware scheduling problems: the objective is to minimize the sum of the total cost of resources and the total weighted completion time in the one machine non-preemptive setting, allowing for arbitrary precedence constraints and release dates. Our algorithm handles general job-dependent resource cost functions. We also analyze the practical performance of our algorithms, showing that it is significantly superior to the theoretical bounds and in fact it is very close to optimal. The analysis is done using simulations and real instances, which are left publicly available for future benchmarks. We also present additional heuristic improvements and we study their performance in other settings.

Suggested Citation

  • Carrasco, Rodrigo A. & Iyengar, Garud & Stein, Cliff, 2018. "Resource cost aware scheduling," European Journal of Operational Research, Elsevier, vol. 269(2), pages 621-632.
    • Handle: RePEc:eee:ejores:v:269:y:2018:i:2:p:621-632
    DOI: 10.1016/j.ejor.2018.02.059
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718302091
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.02.059?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. Richard L. Daniels & Rakesh K. Sarin, 1989. "Technical Note—Single Machine Scheduling with Controllable Processing Times and Number of Jobs Tardy," Operations Research, INFORMS, vol. 37(6), pages 981-984, December.
    2. Van Wassenhove, Luk N. & Baker, Kenneth R., 1982. "A bicriterion approach to time/cost trade-offs in sequencing," European Journal of Operational Research, Elsevier, vol. 11(1), pages 48-54, September.
    3. Leslie A. Hall & Andreas S. Schulz & David B. Shmoys & Joel Wein, 1997. "Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms," Mathematics of Operations Research, INFORMS, vol. 22(3), pages 513-544, August.
    4. 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.
    5. Kailiang Xu & Zuren Feng & Liangjun Ke, 2011. "Single machine scheduling with total tardiness criterion and convex controllable processing times," Annals of Operations Research, Springer, vol. 186(1), pages 383-391, June.
    6. Herroelen, Willy & Leus, Roel, 2005. "Project scheduling under uncertainty: Survey and research potentials," European Journal of Operational Research, Elsevier, vol. 165(2), pages 289-306, September.
    7. Janiak, Adam, 1991. "Single machine scheduling problem with a common deadline and resource dependent release dates," European Journal of Operational Research, Elsevier, vol. 53(3), pages 317-325, August.
    8. Clyde L. Monma & Alexander Schrijver & Michael J. Todd & Victor K. Wei, 1990. "Convex Resource Allocation Problems on Directed Acyclic Graphs: Duality, Complexity, Special Cases, and Extensions," Mathematics of Operations Research, INFORMS, vol. 15(4), pages 736-748, November.
    9. Daniels, Richard L., 1990. "A multi-objective approach to resource allocation in single machine scheduling," European Journal of Operational Research, Elsevier, vol. 48(2), pages 226-241, September.
    10. Janiak, Adam & Kovalyov, Mikhail Y., 1996. "Single machine scheduling subject to deadlines and resource dependent processing times," European Journal of Operational Research, Elsevier, vol. 94(2), pages 284-291, October.
    11. Cheng, T. C. Edwin & Janiak, Adam & Kovalyov, Mikhail Y., 2001. "Single machine batch scheduling with resource dependent setup and processing times," European Journal of Operational Research, Elsevier, vol. 135(1), pages 177-183, November.
    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. Alessandro Hill & Andrea J. Brickey & Italo Cipriano & Marcos Goycoolea & Alexandra Newman, 2022. "Optimization Strategies for Resource-Constrained Project Scheduling Problems in Underground Mining," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3042-3058, November.

    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. Dvir Shabtay & Moshe Kaspi, 2006. "Minimizing the makespan in open‐shop scheduling problems with a convex resource consumption function," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(3), pages 204-216, April.
    2. 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.
    3. Wan, Guohua & Vakati, Sudheer R. & Leung, Joseph Y.-T. & Pinedo, Michael, 2010. "Scheduling two agents with controllable processing times," European Journal of Operational Research, Elsevier, vol. 205(3), pages 528-539, September.
    4. Moshe Zofi & Ron Teller & Moshe Kaspi, 2017. "Maximizing the profit per unit of time for the TSP with convex resource-dependent travelling times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(10), pages 1177-1182, October.
    5. Choi, Byung-Cheon & Yoon, Suk-Hun & Chung, Sung-Jin, 2007. "Single machine scheduling problem with controllable processing times and resource dependent release times," European Journal of Operational Research, Elsevier, vol. 181(2), pages 645-653, September.
    6. Wang, Xiuli & Cheng, T. C. E., 2005. "Single machine scheduling with resource dependent release times and processing times," European Journal of Operational Research, Elsevier, vol. 162(3), pages 727-739, May.
    7. Shabtay, Dvir & Bensoussan, Yaron & Kaspi, Moshe, 2012. "A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system," International Journal of Production Economics, Elsevier, vol. 136(1), pages 67-74.
    8. Hoogeveen, Han, 2005. "Multicriteria scheduling," European Journal of Operational Research, Elsevier, vol. 167(3), pages 592-623, December.
    9. C. Ng & T. Cheng & Adam Janiak & Mikhail Kovalyov, 2005. "Group Scheduling with Controllable Setup and Processing Times: Minimizing Total Weighted Completion Time," Annals of Operations Research, Springer, vol. 133(1), pages 163-174, January.
    10. Chung‐Lun Li & Edward C. Sewell & T. C. E. Cheng, 1995. "Scheduling to minimize release‐time resource consumption and tardiness penalties," Naval Research Logistics (NRL), John Wiley & Sons, vol. 42(6), pages 949-966, September.
    11. Dvir Shabtay & George Steiner, 2008. "The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times," Annals of Operations Research, Springer, vol. 159(1), pages 25-40, March.
    12. Nagar, Amit & Haddock, Jorge & Heragu, Sunderesh, 1995. "Multiple and bicriteria scheduling: A literature survey," European Journal of Operational Research, Elsevier, vol. 81(1), pages 88-104, February.
    13. Daniel Ng, C. T. & Cheng, T. C. Edwin & Kovalyov, Mikhail Y., 2004. "Single machine batch scheduling with jointly compressible setup and processing times," European Journal of Operational Research, Elsevier, vol. 153(1), pages 211-219, February.
    14. Yaron Leyvand & Dvir Shabtay & George Steiner & Liron Yedidsion, 2010. "Just-in-time scheduling with controllable processing times on parallel machines," Journal of Combinatorial Optimization, Springer, vol. 19(3), pages 347-368, April.
    15. Dvir Shabtay & George Steiner, 2007. "Optimal Due Date Assignment and Resource Allocation to Minimize the Weighted Number of Tardy Jobs on a Single Machine," Manufacturing & Service Operations Management, INFORMS, vol. 9(3), pages 332-350, March.
    16. Liu Guiqing & Li Kai & Cheng Bayi, 2015. "Preemptive Scheduling with Controllable Processing Times on Parallel Machines," Journal of Systems Science and Information, De Gruyter, vol. 3(1), pages 68-76, February.
    17. Cheng, T. C. Edwin & Janiak, Adam & Kovalyov, Mikhail Y., 2001. "Single machine batch scheduling with resource dependent setup and processing times," European Journal of Operational Research, Elsevier, vol. 135(1), pages 177-183, November.
    18. Leyvand, Yaron & Shabtay, Dvir & Steiner, George, 2010. "A unified approach for scheduling with convex resource consumption functions using positional penalties," European Journal of Operational Research, Elsevier, vol. 206(2), pages 301-312, October.
    19. Zong-Jun Wei & Li-Yan Wang & Lei Zhang & Ji-Bo Wang & Ershen Wang, 2023. "Single-Machine Maintenance Activity Scheduling with Convex Resource Constraints and Learning Effects," Mathematics, MDPI, vol. 11(16), pages 1-21, August.
    20. Cheng, T. C. E. & Oguz, C. & Qi, X. D., 1996. "Due-date assignment and single machine scheduling with compressible processing times," International Journal of Production Economics, Elsevier, vol. 43(1), pages 29-35, May.

    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:ejores:v:269:y:2018:i:2:p:621-632. 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/eor .

    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.