Untitled
unknown
python
2 years ago
2.9 kB
7
Indexable
#!/usr/bin/env python3 import sys def parse_input(file): with open(file) as f: n = int(f.readline()) p, r, d = [], [], [] for line in f: p_i, r_i, d_i = map(int, line.split()) p.append(p_i) r.append(r_i) d.append(d_i) return n, p, r, d class Scheduler: def __init__(self, n, p, r, d, ub): self.best = [] self.upper_bound = ub self.n = n self.p = p self.r = r self.d = d def compute(best, n, r, p): if len(best) == 0: return [-1] c = 0 schedule = [0 for _ in range(n)] for i in best: t = max(c, r[i]) c = t + p[i] schedule[i] = t return schedule def branch_and_bound(scheduled_tasks, not_sch_tasks, len_of_partial_sch, scheduler): # missed deadline: (∃ Tj ∈ V: max{c, rj} + pj > dj) ⇒ prune this node for i in not_sch_tasks: if scheduler.d[i] < max(len_of_partial_sch, scheduler.r[i]) + scheduler.p[i]: return False # bound on the solution if not not_sch_tasks: if scheduler.upper_bound is None or scheduler.upper_bound > len_of_partial_sch: scheduler.best = scheduled_tasks scheduler.upper_bound = len_of_partial_sch return False else: lower_bound = max(len_of_partial_sch, min(scheduler.r[i] for i in not_sch_tasks)) \ + sum(scheduler.p[i] for i in not_sch_tasks) if scheduler.upper_bound is None: ub = max(scheduler.d[i] for i in not_sch_tasks) if lower_bound > ub: return False elif lower_bound >= scheduler.upper_bound: return False # decomposition, c ≤ min(Tj∈V) {rj }) ⇒ do not backtrack. part_sol = False if len_of_partial_sch <= min(scheduler.r[i] for i in not_sch_tasks): scheduler.best = scheduler.best + scheduled_tasks part_sol = True for i, task in enumerate(not_sch_tasks): new_partial_sch = max(len_of_partial_sch, scheduler.r[task]) + scheduler.p[task] new_not_sch_tasks = [t for idx, t in enumerate(not_sch_tasks) if idx != i] if branch_and_bound(scheduled_tasks + [task], new_not_sch_tasks, new_partial_sch, scheduler): return True return part_sol # Press the green button in the gutter to run the script. if __name__ == '__main__': n, p, r, d = parse_input(sys.argv[1]) scheduler = Scheduler(n, p, r, d, None) scheduled, not_scheduled = [], [i for i in range(n)] branch_and_bound(scheduled, not_scheduled, 0, scheduler) res = compute(scheduler.best, scheduler.n, scheduler.r, scheduler.p) # print(schd.upper_bound) for s in res: print(s) with open(sys.argv[2], "w") as f: for s in res: f.write(str(s) + "\n")
Editor is loading...
Leave a Comment