Page  194 ï~~An foi Efficient Sc r Real-Time hedulin Music Yann Orlarey Grame, 6 quai Jean Mou 69001 Lyon - France. Tel. (33) 78 39 32 02 Abstract: Scheduling problems are important in mo We here present an algorithm allowing to solve these p a bounded low scheduling cost per event in all cir maintain events all the better sorted out as their runnin Introduction

Page  195 ï~~E-R D+I These events are no longer j The current date is increased Ready to run events are retur return As one can see, the events scheduled too late (date e Obviously, other strategies are possible. To solve our problem, there exists a trivial algorithm, c thus consider that the event dates are absolutes 32 bits ur simply consists in using a huge table of 232 entries and date as an index. Events with the same date are chains realistic because of the amount of memory it needs. But it Trivial Algoriti IRes+ t (S) E[0. 3 2 1 3 At the outset, the set of events and the current date is zero. (< ft 00

Page  196 ï~~If not, he puts the order into the appropriate year's rack Once this done, he has but to take the orders in the ck Evidently, on the first day of the following month, orders of the starting month and reclassifies them. Fo each year, the day racks and the month racks are em orders in the month racks, then all the orders for the m At this stage, if we analyze the cost of the treatment more than three times, whatever the advance it is give year's racks, once the month's racks and at las independent of the number of orders already registered. The cost of treatment of an order is therefore very I amount of work accumulated at the beginning of each year. Since Mr Nay is a clever man, he found the solu along the year. To do so, he uses supplementary r reclassification of the following month and an addition Pvervrhiu Mr Minvd rw Â~i little' r rol ncifrntnn wnr

Page  197 ï~~Schedule (e, max (date (e), If the event is late, it is d[3] sif D[3] D[21 D(1] then then then append append append I E3( d(13 E1( append EOrd(OJ J Clock ( sortAlt rnate (S) EOCDCO]] sOro(0o A few events are reclassif4 The low order byte of the c to find the ready to rug These events no longer ar, The current date is increas If the end of level 0 is rea completed and racks b D+1 D~O3J then rtEvent return The events rea to run art It remains to define the ResortEvents routine whi period and the ResortAlternate which reclassifies a f unit.

Page  198 ï~~because it ensures the absence of very unfavourable bounded by a small constant, whatever the advance, number of events already in wait. As it often happens in computer science, an algorithr space. Ours is not an exception for the rule. We hay possible according to the nature of the problem and th more efficient is the algorithm. The simplest case be brings us back to the trivial algorithm of the beginnir References [1] Knuth D. I. [19731: ((Sorting and Searchingv The Art of Computer Programming vol. 3. Addison Wesley.