#!/usr/bin/python # Christoph Durr, CNRS, 2010 ---- implements the algorithm from # Polynomial Time Algorithms for Minimum Energy Scheduling with # Philippe Baptiste, Marek Chrobak, ESA, 136-150, 2007. However this # implementation does not in time O(n^5), but in O(n^7). The places # for improvement are the function P, were we tried here to stick # closest to the recursion of the paper, as well as the function prev, # which should be precomputed to improve running time. # Usage: execute with two command line arguments. The first one # contains release times/processing times/deadlines for all jobs, as # in "37/8/46 38/2/47 10/5/25" for example and the second contains the # boot-time L. from sys import * from copy import * # global variables: # n = number of jobs # J = list of jobs # L = large gap threshold # -------------------------------------------------------------------- Job class Job: '''a job has release time r, processing time p, deadline d, name i. Jobs are ordered according to increasing deadlines. ''' def __init__(self,r,p,d,i): self.r=r self.p=p self.d=d self.i=i def __cmp__(self, oth): return cmp((self.d,self.r,self.i), (oth.d, oth.r, oth.i)) def __str__(self): return "" \ % (self.i, self.r, self.p, self.d) def prev(k,t): '''maximum rj among jobs j<=k with rjr: r = rj return r # -------------------------------------------------------------------- Skeleton class Skeleton: '''a skeleton is the support of some schedule. It consists of a non-empty ordered sequence of blocks. A block is a pair of the form (starttime,endtime).''' def __init__(self,b): self.b = b def __str__(self): return str(self.b) def gaps(self): return len(self.b)-1 def start(self): return self.b def end(self): return self.b[-1] def rightFill(self, p): '''add support from the end of the skeleton to the right''' s,e = self.b[-1] self.b[-1] = (s,e+p) def leftFill(self, dk, p): '''add support from dk to the skeleton to the left, possibly wrapping last blocks.''' assert p>0 previousStart = self.start() # create a new last block (s1,e1) = (dk-p, dk) while len(self.b)>0 and self.end() >= s1: (s0,e0) = self.b.pop() s1 -= e0-s0 self.b.append((s1,e1)) return s1>=previousStart def __add__(s1,s2): '''concatenate two skeletons''' assert s1.end()<=s2.start(), "combine overlapping skeletons" if s1.end()0 and J[i].r<=t] if not pending: return None # no job available i = min(pending) # most urgent pending job di = J[i].d if di<=t: return None # job expired # next jobs to interrupt i moreUrgent = [J[j].r for j in range(i) if p[j]>0 and j!=i] Ci = t+p[i] # ideal completion time # nextEvent: either completion of i, # ... or end of block, or interruption nextEvent = min(moreUrgent+[Ci, endBlock]) S.append((t, i, nextEvent)) p[i] -= nextEvent-t t = nextEvent # move to next event # verify that all jobs completed if [i for i in p if p[i]>0]: return None return S def printSchedule(S): for (s,i,e) in S: if s>=0: # don't show dummy job execution print "" \ % (J[i].i, s, e) # -------------------------------------------------------------------- U UU = {} # memoization def U(s,k,g): '''Maximal makespan schedule over jobs j<=k with r_j>=r_s and at most g gaps.''' if (s,k,g) in UU: return UU[s,k,g] rs = J[s].r if k<0: # empty schedule UU[s,k,g] = Skeleton([(rs,rs)]) return UU[s,k,g] Usk1g = U(s,k-1,g) rk = J[k].r pk = J[k].p dk = J[k].d # k out of range, or pb unfeasible if rk < rs or not Usk1g: UU[s,k,g] = Usk1g return UU[s,k,g] # -- case 0 if rk > Usk1g.end(): best = Usk1g else: best = None # optimal solution # we use a single loop so we can interrupt with a single break for l,h in [(s,0)]+[(l,h) for l in range(k) for h in range(g+1)]: # -- case 1 p,a = P(s,k,h,l) if p>pk: continue if hpk-p and \ b.end()>prev(k-1,dk): t = dk-(pk-p) c = a + b if c.leftFill(dk,pk-p): best = c break # -- case 2 b = U(l,k-1,g-h) if not b: continue if p prev(k-1,dk): c = a + b if c.leftFill(dk,pk-p): best = c break # -- case 3 t = b.end() + pk - p if p<=pk and \ rk <= b.end() and \ dk - b.end() > pk - p and \ b.end() > prev(k-1, t+1): #t+1 for frugality c = a + b c.rightFill(pk-p) if best==None or c.end() > best.end(): best = c UU[s,k,g] = best return best # -------------------------------------------------------------------- P PP = {} # memoization def P(s,k,g,l): '''basically minimal processing time p such that the instance for pk<-p has a (s,k)-schedule with makespan r_l. Returns couple with this value and the schedule.''' if (s,k,g,l) in PP: return PP[s,k,g,l] rs = J[s].r rl = J[l].r rk = J[k].r pk = J[k].p a = U(s,k-1,g) if rs>rl or not a: PP[s,k,g,l] = ((),None) return PP[s,k,g,l] if rs==rl or a.end()>=rl: PP[s,k,g,l] = (0, Skeleton([(rs,rs)])) return PP[s,k,g,l] best = ((),None) # () == +infinity in python for h in range(g+1): a = U(s,k-1,h) if not a: continue for j in range(k): rj = J[j].r if rs <= rj and rj <= rl and \ prev(k-1,rj) < a.end() and \ a.end() < rj and \ rk <= a.end(): p,b = P(j,k,g-h,l) if p>pk: continue q = rj-a.end()+p if qu.end()] if not nextRelease: alt = (L*g, u) else: rj,j = min(nextRelease) alt = (L*g + rj - u.end() + E[j], u+E[j]) if alt" # remove dummy job induced cost printSchedule(S) for i in range(len(sk.b)-1): s = sk.b[i] e = sk.b[i+1] c = min(e-s,L) if s>=0: # remove gap after dummy job print ""%(c,s,e) else: print " objvalue=0 objfct=feasibility >" for j in J: if j!=dummy: print str(j) print ""