# Untitled

unknown
python
7 months ago
2.9 kB
3
Indexable
Never
```#!/usr/bin/env python3
import sys

def parse_input(file):
with open(file) as f:
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

# missed deadline: (∃ Tj ∈ V: max{c, rj} + pj > dj) ⇒ prune this node
if scheduler.d[i] < max(len_of_partial_sch, scheduler.r[i]) + scheduler.p[i]:
return False

# bound on the solution
if scheduler.upper_bound is None or scheduler.upper_bound > len_of_partial_sch:
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):
part_sol = True

new_not_sch_tasks = [t for idx, t in enumerate(not_sch_tasks) if idx != i]
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")```