The basic scheduling issue is examined in this chapter. On n identical computers with bounded capacity, n deterministic jobs need to be scheduled offline. Each work has a start time, a finish time, a processing time, and a machine capacity requirement. The purpose is to schedule all of the jobs no proactively in their start-time–end-time windows, subject to machine capacity limits so that the overall busy time of the machines is minimized. Minimizing the overall busy time for the scheduling of several identical machines is the name we give to this issue (MinTBT). Power-aware scheduling for Cloud computing, optical network design, customer service systems, and other relevant fields can all benefit from solving this issue. In the particular case where all jobs have the same process time and can be scheduled in a set time interval, scheduling to reduce busy time is already NP-hard. The 5-approximation approach for exceptional situations utilizing the first-fit-decreasing (FFD) algorithm is one of the best-known solutions to this problem. In this chapter, we suggest and demonstrate a modified first-fit-decreasing-earliest 3-approximation technique for the general case and gain further results for particular situations. Then, we demonstrate how our findings might be used in cloud computing to increase energy efficiency.

Energy-efficient scheduling; offline algorithm; online algorithm; MFFDE algorithm; BFF algorithm; GRID algorithm; approximation ratio; competitive ratio

[1]. Hoogeveen JA, van de Velde SL, Veltman B. Complexity of scheduling multiprocessor tasks with prespecified processor allocations. Discrete Appl Math. Vol.55, Issue.3, pp.259–272, 1994.
[2]. Khandekar R, Schieber B, Shachnai H, Tamir T. Minimizing busy time in multiple machine real-time scheduling. Proceedings of IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2010). Chennai, India: LIPIcs, Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik; Vol.8, pp.169–180, 2010.
[3]. Brucker P. Scheduling algorithms 5th ed. Berlin, Heidelberg, New York: Springer; 2007.
[4]. Beloglazov A, Buyya R, Lee YC, Zomaya AY. A taxonomy and survey of energy-efficient data centers and Cloud computing systems. Adv Comput. Vol.82, pp.47–111, 2011.
[5]. Jing SY, Ali S, She K, Zhong Y. State-of-the-art research study for green Cloud computing. J Supercomput, pp.1–24, 2011.
[6]. Graham RL. Bounds on multiprocessing timing anomalies. SIAM J Appl Math., Vol.17, Issue.2, pp.416–429, 1969.
[7]. Kleinberg JM, Tardos E. Algorithm design Boston, MA: Addison-Wesley: Pearson Education, Inc.; 2006.
[8]. Kovalyov MY, Ng CT, Cheng TCE. Fixed intervals scheduling: models, applications, computational complexity and algorithms. Eur J Oper Res., Vol.178, Issue.2, pp.331–342, 2007.
[9]. Beloglazov A, Abawajy JH, Buyya R. Energy-aware resource allocation heuristics for efficient management of data centers for Cloud computing. Future Gen Comput Syst. Vol.28, Issue.5, pp.755–768, 2012.
[10]. Winkler P, Zhang L. Wavelength assignment generalized interval graph coloring. Proceedings of fourteenth annual ACM-SIAM symposium on discrete algorithms (SODA 2003) Baltimore, MD: ACM/SIAM; pp.830–831, 2003.
[11]. Flammini M, Monaco G, Moscardelli L, et al. Minimizing total busy time in parallel scheduling with application to optical networks. Theor Comput Sci., Vol.411, Issue.40–42, pp.3553–3562, 2010.
[12]. Kolen AW, Lenstra JK, Papadimitriou CH, Spieksma FC. Interval scheduling: a survey. Nav Res Log., Vol.54, Issue.5, pp.530–543, 2007.
[13]. Srikantaiah S, Kansal A, Zhao F. Energy aware consolidation for Cloud computing. Proceedings of USENIX workshop on power aware computing and systems (HotPower 2008) San Diego, CA: USENIX; pp.10–14, 2008.
[14]. Lee YC, Zomaya AY. Energy efficient utilization of resources in Cloud computing systems. J Supercomput. Vol.60, Issue.2, pp.268–280, 2012.
[15]. Liu H, Xu C, Jin H, Gong J, Liao X. Performance and energy modeling for live migration of virtual machines, the 20th international symposium on high performance distributed computing. pp.171–182, 2011.
[16]. Kim KH, Beloglazov A, Buyya R. Power-aware provisioning of virtual machines for real-time Cloud services. Concurr Comput Pract Exp. Vol.23, Issue.13, pp.1491–1505, 2011.
[17]. Mathew V, Sitaraman RK, Shenoy PJ. Energy-aware load balancing in content delivery networks. Proceedings of IEEE INFOCOM Orlando, FL: IEEE; pp.954–962, 2012.
[18]. Rao L, Liu X, Xie L, Liu W. Minimizing electricity cost: optimization of distributed internet data centers in a multi-electricity-market environment. Proceedings of IEEE INFOCOM 2010 San Diego, CA: IEEE; pp.1145–1153, 2010.
[19]. Lin M, Wierman A, Andrew LLH, Thereska E. Dynamic right-sizing for power-proportional data centers. Proceedings of IEEE INFOCOM 2011 Shanghai, China: IEEE; pp.1098–1106, 2011.
[20]. Mertzios GB, Shalom M, Voloshin A, Wong PWH, Zaks S. Optimizing busy time on parallel machines. Proceedings of IPDPS Shanghai, China: IEEE; pp.238–248, 2012.