Competitive Non-migratory Scheduling forFlow Time and EnergyTak-Wah LamDepartment of Computer ScienceUniversity of Hong [email protected] LeeDepartment of Computer ScienceUniversity of Hong [email protected] K. K. ToDepartment of Computer ScienceUniversity of Liverpool, [email protected] W. H. Wong∗Department of Computer ScienceUniversity of Liverpool, [email protected] usage has been an important concern in recent re-search on online scheduling. In this paper we extend thestudy of the tradeoff between flow time and energy from thesingle-processor setting [8, 6] to the multi-processor setting.Our main result is an analysis of a simple non-migratory on-line algorithm called CRR (classified round robin) on m ≥ 2processors, showing that its flow time plus energy is withinO(1) times of the optimal non-migratory offline algorithm,when the maximum allowable speed is slightly relaxed. Thisresult still holds even if the comparison is made against theoptimal migratory offline algorithm (the competitive ratioincreases by a factor of 2.5). As a special case, our workalso contributes to the traditional online flow-time schedul-ing. Specifically, for minimizing flow time only, CRR canyield a competitive ratio one or even arbitrarily smaller thanone, when using sufficiently faster processors. Prior to ourwork, similar result is only known for online algorithms thatneeds migration [21, 23], while the best non- migratory resultcan ac hieve an O(1) competitive ratio [14].The above result stems from an interesting observationthat there always exists some optimal migratory schedu le Sthat can be converted (in an offline sense) to a non-migratoryschedule S!with a moderate increase in flow time plus en-ergy. More importantly, this non-migratory schedule alwaysdispatches jobs in the same way as CRR.Categories and Subject DescriptorsF.2.2 [Analysis of Algorithms and Problem Complex-ity]: Nonnumerical Algorithms and Problems—Sequencingand scheduling∗This research is partly supported by EPSR C GrantEP/E028276/1.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SPAA’08, June 14–16, 2008, Munich, Germany.Copyright 2008 ACM 978-1-59593-973-9/08/06 ...$5.00.General TermsAlgorithms, Performance, TheoryKeywordsOnline scheduling algorithms, competitive analysis, dynamicspeed scaling, energy minimization1. INTRODUCTIONEnergy consumption has become a key issue in the de-sign of modern processors. This is essential not only forbattery-operated mobile devices with single processors butalso for server farms or laptops with multi-core processors. Apopular technology to reduce energy usage is dynamic speedscaling (see, e.g., [9, 15, 24, 28]) where the processor canvary its speed dynamically. Running a job at a slower speedis more energy efficient, yet it takes longer time and mayaffect the performance. In the past few years, a lot of efforthas been devoted to revisiting classical scheduling problemswith dynamic speed scaling and energy concern taken intoconsideration (e.g., [29, 7, 1, 8, 11, 2, 10, 26, 16]; see [17] forasurvey). Thechallengebasicallyarisesfromtheconflictingobjectiv es of providing good “quality of service” (QoS) andconserving energy.One commonly used QoS measurement for scheduling jobson a processor is the total flow time (or equivalently, averageresponse time). Here, jobs witharbitrarysizearereleasedat unpredictable times and the flow time of a job is thetime elapsed since it arrives until it is completed. Whenenergy is not a concern, the objective of a scheduler is sim-ply to minimize the total flow time of all jobs. The studyof energy-efficient scheduling was initiated by Yao, Demersand Shenker [29]. They considered deadline scheduling onamodelwheretheprocessorcanrunatanyspeedbetween0and∞,andincursanenergyofsαper unit time whenrunning at sp eed s,whereα ≥ 2(typically2or3[9,22]).This model, which we call infinite speed model, also pavesthe way for studying scheduling that minimizes both th eflow time and energy. In particular, Pruhs et al. [27] stud-ied offline scheduling for minimizing the total flow time on asingle processor with a given amount of energy. They gave apolynomial time optimal algorithm for the special case whenjobs are of unit size. However, this problem does not admitany constant competitive online algorithm even if jobs areof unit size [8].Flow time and energy. To better understand the trade-off between flow time and energy, Albers and Fujiwara [1]proposed combining the dual objectives into a single objec-tive of minimizing the sum of total flow time and energy.The intuition is that, from an economic viewpoint, it canbe assumed that users are willing to pay a certain units(say, ρ units) of energy to reduce one unit of flow time. Bychanging the units of time and energy, one can further as-sume that ρ =1andthuswouldliketooptimizetotalflowtime plus energy. Albers and Fujiwara presented an onlinealgorithm that is 8.3e(3+√52)α-competitive for jobs of unitsize. This result was recently improved by Bansal et al. [8],who gave a 4-competitive algorithm for jobs of unit size.They also considered the case for jobs with arbitrary sizeand weigh t, and presen ted an O(1)-competitive online algo-rithm for minimizing weighted flow time plus energy (pre-cisely, the competitive ratio is µ"γ1,where$ is any positiveconstant, µ"=max{(1 + 1/$), (1 + $)α},andγ1< 2α/ ln α).The infinite speed model has provided a conv enient modelfor studying power management, yet it is not realistic to as-sume infinite speed. Recently, Chan et al. [11] introducedthe bounded speed model, where the sp eed can be scaled be-tween 0 and some maximum T .Bansaletal.[6]successfullyadapted the previous results on minimizing flow time plusenergy to this model. For jobs of unit size and unit weight,they gave a 4-competitive online algorithm. For jobs of ar-bitrary size and weight, they gave a (µ"γ2)-competitive al-gorithm that uses a processor with maximum speed (1+ $)Tfor any $>0, where γ2=(2+o(1))α/ ln α.Multiprocessor scheduling. All the results above areabout single-processor scheduling. In the older