Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Scheduling on a single machine under time-of-use electricity tariffs

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We consider the problem of scheduling jobs on a single machine to minimize the total electricity cost of processing these jobs under time-of-use electricity tariffs. For the uniform-speed case, in which all jobs have arbitrary power demands and must be processed at a single uniform speed, we prove that the non-preemptive version of this problem is inapproximable within a constant factor unless\(\text {P} = \text {NP}\). On the other hand, when all the jobs have the same workload and the electricity prices follow a so-called pyramidal structure, we show that this problem can be solved in polynomial time. For the speed-scalable case, in which jobs can be processed at an arbitrary speed with a trade-off between speed and power demand, we show that the non-preemptive version of the problem is strongly NP-hard. We also present different approximation algorithms for this case, and test the computational performance of these approximation algorithms on randomly generated instances. In addition, for both the uniform-speed and speed-scaling cases, we show how to compute optimal schedules for the preemptive version of the problem in polynomial time.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17

Similar content being viewed by others

Notes

  1. A\(\rho \)-approximation algorithm finds a solution whose objective value is within a factor\(\rho \) of the optimal value, and runs in time polynomial in the input size. The factor\(\rho \) is known as theperformance guarantee.

References

  • Albers, S. (2010). Energy-efficient algorithms.Communications of the ACM,53(5), 86–96.

    Article  Google Scholar 

  • Albers, S., & Fujiwara, H. (2007). Energy-efficient algorithms for flow time minimization.ACM Transactions on Algorithms,3(4), 49-1–49-17.

  • Antoniadis, A., & Huang, C. (2013). Non-preemptive speed scaling.Journal of Scheduling,16(4), 385–394.

    Article  Google Scholar 

  • Antoniadis, A., Kling, P., Ott, S., & Riechers, S. (2015). Speed scaling with variable electricity rates and speed limits. InProceedings of the 12th workshop on models and algorithms for planning and scheduling problems (MAPSP 2015).

  • Bampis, E., Letsios, D., Milis, I., & Zois, G. (2012). Speed scaling for maximum lateness. In J. Gudmundsson, J. Mestre, & T. Viglas (Eds.),18th international conference on computing and combinatorics (COCOON 2012),volume 7434 ofLecture Notes in Computer Science, (pp. 25–36). Springer.

  • Bampis, E., Kononov, A., Letsios, D., Lucarelli, G., & Sviridenko, M. (2013). Energy efficient scheduling and routing via randomized rounding. In A. Seth, & N. K. Vishnoi (Eds.),IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013),volume 24 ofLeibniz International Proceedings in Informatics, (pp. 449–460). Schloss Dagstuhl.

  • Bampis, E., Kononov, A., Letsios, D., Lucarelli, G., & Nemparis, I. (2015). From preemptive to non-preemptive speed-scaling scheduling.Discrete Applied Mathematics,181, 11–20.

    Article  Google Scholar 

  • Bansal, N., Pruhs, K., & Stein, C. (2007). Speed scaling for weighted flow time. InProceedings of the 18th annual ACM-SIAM symposium on discrete algorithms (SODA07), (pp. 805–813).

  • Braithwait, S., Hansen, D., & O’Sheasy, M. (2007). Retail electricity pricing and rate design in evolving markets. Technical report, Edison Electric Institute.

  • Brooks, D. M., Bose, P., Schuster, S. E., Jacobson, H., Kudva, P. N., Buyuktosunoglu, A., et al. (2000). Power-aware microarchitecture: Design and modeling challenges for next-generation microprocessors.Micro, IEEE,20(6), 26–44.

    Article  Google Scholar 

  • Castro, P. M., Harjunkoski, I., & Grossmann, I. E. (2009). New continuous-time scheduling formulation for continuous plants under variable electricity cost.Industrial & Engineering Chemistry Research,48(14), 6701–6714.

    Article  Google Scholar 

  • Cohen-Addad, V., Li, Z., Mathieu, C., & Milis, I. (2014). Energy-efficient algorithms for non-preemptive speed-scaling. InProceedings of the 12th workshop on approximation and online algorithms (WAOA 2014).

  • Detti, P., Hurkens, C., Agnetis, A., & Ciaschetti, G. (2009). Optimal packet-to-slot assignment in mobile telecommunications.Operations Research Letters,37(4), 261–264.

    Article  Google Scholar 

  • Fang, K., Uhan, N. A., Zhao, F., & Sutherland, J. W. (2011). A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction.Journal of Manufacturing Systems,30(4), 234–240.

    Article  Google Scholar 

  • Fang, K., Uhan, N. A., Zhao, F., & Sutherland, J. W. (2013). Flow shop scheduling with peak power consumption constraints.Annals of Operations Research,206(1), 115–145.

    Article  Google Scholar 

  • Garey, M. R., & Johnson, D. S. (1979).Computers and intractability: A guide to the theory of NP-completeness. New York: W.H. Freeman.

    Google Scholar 

  • Irani, S., & Pruhs, K. R. (2005). Algorithmic problems in power management.SIGACT News,36(2), 63–76.

    Article  Google Scholar 

  • Kannan, R., & Wei, S. (2006). Approximation algorithms for power-aware scheduling of wireless sensor networks with rate and duty-cycle constraints. In P. B. Gibbons, T. Abdelzaher, J. Aspnes, & R. Rao (Eds.),2nd IEEE international conference on distributed computing in sensor systems (DCOSS 2006),volume 4026 ofLecture Notes in Computer Science, (pp. 463–479). Springer.

  • Kulkarni, J., & Munagala, K. (2013). Algorithms for cost-aware scheduling. In T. Erlebach & G. Persiano (Eds.),10th international workshop on approximation and online algorithms (WAOA 2012),volume 7846 ofLecture Notes in Computer Science, (pp. 201–214). Springer.

  • Mitra, S., Grossmann, I. E., Pinto, J. M., & Arora, N. (2012). Optimal production planning under time-sensitive electricity prices for continuous power-intensive processes.Computers & Chemical Engineering,38, 171–184.

    Article  Google Scholar 

  • Moon, J.-Y., Shin, K., & Park, J. (2013). Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency.International Journal of Advanced Manufacturing Technology,68(1–4), 523–535.

    Article  Google Scholar 

  • Mouzon, G., Yildirim, M. B., & Twomey, J. (2007). Operational methods for minimization of energy consumption of manufacturing equipment.International Journal of Production Research,45(18–19), 4247–4271.

    Article  Google Scholar 

  • Mudge, T. (2001). Power: A first-class architectural design constraint.Computer,34(4), 52–58.

    Article  Google Scholar 

  • Park, C. W., Kwon, K. S., Kim, W. B., Min, B. K., Park, S. J., Sung, I. H., et al. (2009). Energy consumption reduction technology in manufacturing—A selective review of policies, standards, and research.International Journal of Precision Engineering and Manufacturing,10(5), 151–173.

    Article  Google Scholar 

  • Shapiro, S., & Tomain, J. (2005). Rethinking reform of electricity markets.Wake Forest Law Review,40, 497–543.

    Google Scholar 

  • Subai, C., Baptiste, P., & Niel, E. (2006). Scheduling issues for environmentally responsible manufacturing: The case of hoist scheduling in an electroplating line.International Journal of Production Economics,99(1), 74–87.

    Article  Google Scholar 

  • Sun, Z., Biller, S., Gu, F., & Li, L. (2011). Energy consumption reduction for sustainable manufacturing systems considering machines with multiple-power states. InASME 2011 international manufacuring science and engineering conference, Corvallis, Oregon, USA, June 13–17.

  • Wan, G., & Qi, X. (2010). Scheduling with variable time slot costs.Naval Research Logistics,57(2), 159–171.

    Google Scholar 

  • Wang, J., Li, J., & Huang, N. (2009). Optimal scheduling to achieve energy reduction in automotive paint shops. In2009 ASME manufacturing science and engineering conference, West Lafayette, Indiana, USA, October 4–7.

  • Yao, F., Demers, A., & Shenker, S. (1995). A scheduling model for reduced CPU energy. InProceedings of the 36th Annual Symposium on Foundations of Computer Science, (pp. 374–382).

Download references

Author information

Authors and Affiliations

  1. College of Management and Economics, Tianjin University, Tianjin, 300072, China

    Kan Fang

  2. Mathematics Department, United States Naval Academy, Annapolis, MD, 21402, USA

    Nelson A. Uhan

  3. Environmental and Ecological Engineering and School of Mechanical Engineering, Purdue University, West Lafayette, IN, 47904, USA

    Fu Zhao

  4. Environmental and Ecological Engineering, Purdue University, West Lafayette, IN, 47904, USA

    John W. Sutherland

Authors
  1. Kan Fang

    You can also search for this author inPubMed Google Scholar

  2. Nelson A. Uhan

    You can also search for this author inPubMed Google Scholar

  3. Fu Zhao

    You can also search for this author inPubMed Google Scholar

  4. John W. Sutherland

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toNelson A. Uhan.

Appendix: Tables of results from computational experiments

Appendix: Tables of results from computational experiments

See Tables2,3,4 and5.

Table 2 Average ratio between the total electricity costs of schedules obtained by Algorithms 4.2, 4.3, 4.4 and an optimal preemptive schedule
Table 3 Average ratio between total electricity costs of schedules obtained by Algorithm 4.2 and an optimal preemptive schedule
Table 4 Average ratio between total electricity costs of schedules obtained by Algorithm 4.3 and an optimal preemptive schedule
Table 5 Average ratio between total electricity costs of schedules obtained by Algorithms 4.3 and 4.2

Rights and permissions

About this article

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp