""" indsched.py : construction routines for a real-world scheduling problem Copyright Joao Pedro PEDROSO, FCUP/DCC, 09/2004 jpp@ncc.up.pt http:///www.ncc.up.pt/~jpp/schedul ********************************************************************** """ import random from copy import * from numarray import * Infinity = 9.999e99 class SolStruct: """a class for holding solution information""" def __init__(self, inst): """inst -> instance with data""" self.x = {} # list of operations in each machine # e.g., self.x = { 1:[1,4], 2:[2,3,5], 3:[6,7,8] } self.y = {} # machine assigned to each operation self.z = {} # sequence order for op. in its machine for m in inst.MACHS: self.x[m] = [] for i in inst.OPS: self.y[i] = -1 self.z[i] = -1 def append(self, o, m): """append operation 'o' to machine 'm'""" self.x[m].append(o) self.y[o] = m self.z[o] = len(self.x[m])-1 def remove(self, o, m): """remove operation 'o' from machine 'm'""" self.x[m].remove(o) self.y[o] = -1 self.z[o] = -1 def __str__(self): """convert to string""" s = "" for m in self.x.keys(): s += "machine %d:" % m for o in self.x[m]: s += " %d" % o s += "\n" return s class Solution(SolStruct): """keep a solution, together with the makespan calculation information""" def __init__(self, inst): SolStruct.__init__(self, inst) uprec = deepcopy(inst.prec) # inicialize unscheduled predecessors of each operation self.s = {} self.f = {} self.makespan = 0 self.inst = inst # necessary for calculating makespan def append(self,o,m): """ * insert operation * calculate makespan for each machine, including cleaning time """ inst = self.inst # shortcut # !!! should assert that all job precedences are scheduled !!! if self.x[m] == []: # first operation on machine t = inst.C[0,o] else: p = self.x[m][-1] # previous operation t = self.f[p] + inst.C[p,o] # concluding time o previous + changeover # transfer times for p in inst.prec[o]: pm = self.y[p] # machine of previous operation on the job t = max(t, self.f[p] + inst.U[pm,m]) # update class'es data SolStruct.append(self,o,m) self.f[o] = t + inst.D[o] # operation finishing time self.s[m] = self.f[o] + inst.C[o,0] # makespan for machine m # on ill-conditioned instances, adding one operation might reduce # the machine's makespan; so we have to recompute it from scratch self.makespan = 0 for mm in self.x.keys(): if self.x[mm] != []: self.makespan = max(self.makespan,self.s[mm]) def remove(self,o,m): """remove operation, update makespans""" SolStruct.remove(self,o,m) del self.f[o] if self.x[m] == []: del self.s[m] else: last = self.x[m][-1] self.s[m] = self.f[last] + C[last,0] self.makespan = 0 for mm in self.x.keys(): if self.x[mm] != []: self.makespan = max(self.makespan,self.s[mm]) def check(self,o,m): """check makespan for appending 'o' on machine 'm', but do not actually do it""" inst = self.inst # shortcut if self.x[m] == []: # first operation on machine t = inst.C[0,o] else: p = self.x[m][-1] # previous operation t = self.f[p] + inst.C[p,o] # concluding time o previous + changeover # transfer times for p in inst.prec[o]: pm = self.y[p] # machine of previous operation on the job t = max(t, self.f[p] + inst.U[pm,m]) newspan = t + inst.D[o] + inst.C[o,0] if newspan < self.makespan: for mm in self.x.keys(): if self.x[mm] != [] and mm != m: newspan = max(newspan,self.s[mm]) return newspan def __str__(self): """convert to string""" s = "" for m in self.x.keys(): s += "machine %d:" % m for o in self.x[m]: s += " %d" % o s += "\tt=%d\n" % self.s[m] for o in self.f.keys(): s += "f[%d] = %d\n" % (o, self.f[o]) s += 'makespan: %d' % self.makespan return s def RandomConstruct(inst): """construct a random, feasible solution""" sol = Solution(inst) # start scheduling uprec = deepcopy(inst.prec) # inicialize unscheduled predecessors of each operation R = inst.OPS[:] # R -> keep unscheduled operations while R != []: F = [] for o in R: if uprec[o] == []: F.append(o) o = random.choice(F) m = random.choice(inst.COMP[o]) # print 'uprec:', uprec # print 'R:', R # print 'F:', F, '\to=', o, 'm=', m sol.append(o,m) for i in inst.succ[o]: uprec[i].remove(o) R.remove(o) # print "sol=\n", sol, "\n" return sol def Makespan(sol): """compute makespan of sol""" # start scheduling inst = sol.inst # shortcut uprec = deepcopy(inst.prec) # inicialize unscheduled predecessors of each operation # add predecessors on machines to operations precedences machs = sol.x.keys() for m in machs: ops = sol.x[m] for i in range(1,len(ops)): prev = ops[i-1] curr = ops[i] uprec[curr].append(prev) # schedule and compute makespan R = inst.OPS[:] # R -> keep unscheduled operations R = [] for m in machs: for o in sol.x[m]: R.append(o) f = {} while R != []: F = [] for o in R: if uprec[o] == []: F.append(o) assert F != [] for o in F: m = sol.y[o] # machine where o is processed i = sol.z[o] # order of op o on machine m # print i, 'th op in machine', m if i==0: # first operation on machine t = inst.C[0,o] else: p = sol.x[m][i-1] t = f[p] + inst.C[p,o] # transfer times for p in inst.prec[o]: pm = sol.y[p] t = max(t, f[p] + inst.U[pm,m]) f[o] = t + inst.D[o] # operation finishing time for j in inst.succ[o]: # successors in the job uprec[j].remove(o) if i < len(sol.x[m])-1: # successor in the machine q = sol.x[m][i+1] uprec[q].remove(o) R.remove(o) t = 0 s = {} for m in inst.MACHS: if sol.x[m] != []: o = sol.x[m][-1] # last operation on machine s[m] = f[o] + inst.C[o,0] # makespan for machine m, including cleaning t = max(t,s[m]) return s,t def GreedyConstruct(inst): """construct a greedy, feasible solution""" sol = Solution(inst) # start scheduling uprec = deepcopy(inst.prec) # inicialize unscheduled predecessors of each operation R = inst.OPS[:] # R -> keep unscheduled operations while R != []: F = [] for o in R: if uprec[o] == []: F.append(o) # test appending each operation to each possible machine t_star = Infinity for o in F: for m in inst.COMP[o]: # machines compatible with this operation # print 'op', o, 'mach', m makespan = sol.check(o,m) if makespan < t_star: t_star, m_star, o_star = makespan, m, o # print 'uprec:', uprec # print 'R:', R sol.append(o_star,m_star) # print 'F:', F, '\to=', o_star, 'm=', m_star for i in inst.succ[o_star]: uprec[i].remove(o_star) R.remove(o_star) # print "sol=\n", sol, "\n" return sol class RestrCandList: """manage an alpha-controlled restricted candidate list""" def __init__(self): self.RCL = {} def push(self, op, mach, t): """add onem move to the list""" self.RCL[(op,mach)] = t def pop(self, alpha): """pop a random move within alpha% of the best""" keys = self.RCL.keys() t_min = self.RCL[ keys[0] ] t_max = t_min for k in keys[1:]: t = self.RCL[k] if t < t_min: t_min = t if t > t_max: t_max = t cand = [] # list from which actual move will be drawn cut = t_min + (t_max-t_min)*alpha; for (o,m) in keys: t = self.RCL[(o,m)] if t <= cut: cand.append((o,m,t)) assert cand != [] return random.choice(cand) def choice(self): """pop a random move within alpha% of the best, alpha drawn randomly""" alpha = random.random() return self.pop(alpha) def SemiGreedyConstruct(inst): """construct a semi-greedy, feasible solution""" sol = Solution(inst) # start scheduling uprec = deepcopy(inst.prec) # inicialize unscheduled predecessors of each operation R = inst.OPS[:] # R -> keep unscheduled operations while R != []: F = [] for o in R: if uprec[o] == []: F.append(o) # test appending each operation to each possible machine rcl = RestrCandList() for o in F: for m in inst.COMP[o]: makespan = sol.check(o,m) rcl.push(o,m,sol.makespan) o_star, m_star, t_star = rcl.choice() sol.append(o_star, m_star) # print 'F:', F, '\to=', o_star, 'm=', m_star for i in inst.succ[o_star]: uprec[i].remove(o_star) R.remove(o_star) return sol def IteratedSemiGreedy(inst, iters): best = SemiGreedyConstruct(inst) for i in range(iters): sol = SemiGreedyConstruct(inst) if sol.makespan < best.makespan: best = sol return best if __name__ == '__main__': from instance import * # use sample 'gbl_inst' variable defined there sol = RandomConstruct(gbl_inst) print "RandomConstruct=\n", sol print 'x:', sol.x print 'f:', sol.f print sol.s, sol.makespan s,t = Makespan(sol) print s,t print sol = GreedyConstruct(gbl_inst) print "GreedyConstruct=\n", sol print 'x:', sol.x print 'f:', sol.f print sol.s, sol.makespan s,t = Makespan(sol) print s,t print sol = SemiGreedyConstruct(gbl_inst) print "SemiGreedyConstruct=\n", sol print 'x:', sol.x print 'f:', sol.f print sol.s, sol.makespan s,t = Makespan(sol) print s,t print sol = IteratedSemiGreedy(gbl_inst,100) print "SemiGreedyConstruct=\n", sol print 'x:', sol.x print 'f:', sol.f print sol.s, sol.makespan s,t = Makespan(sol) print s,t print