IoIV HW2 Q3.py

hw2-q3.py

from math import ceil
from random import randint, random
from math import e, pow
from copy import deepcopy
from time import time

def swap(transmission: list, period: list, i=None, j=None) -> tuple:
    if i is None:
        i, j = randint(0, n-1), randint(0, n-1)
    transmission_time[i], transmission_time[j] = transmission_time[j],transmission_time[i]
    period[i], period[j] = period[j], period[i]
    return i, j

def calculate(n: int, transmission_time: list, period: list) -> (int, bool):
    total = 0
    for i in range(n):
        block_time = max(transmission_time[i:])
        lhs = block_time
        rhs = -1
        while lhs != rhs:
            if rhs != -1:
                lhs = rhs
            s = 0
            for j in range(i):
                s += ceil((lhs+tau) / period[j]) * transmission_time[j]
            rhs = block_time + s
            if rhs + transmission_time[i] > period[i]:
                return 0, True
        total += lhs + transmission_time[i]
    return total, False

class Solution():

    def __init__(self, transmission_time: list, period: list, value: float):
        self.transmission_time = deepcopy(transmission_time)
        self.period = deepcopy(period)
        self.value = value
   

start_time = time()
n = int(input())
tau = float(input())

priority = []
transmission_time = []
period = []

for i in range(n):
    s = input().lstrip().rstrip().split(' ')
    priority.append(int(s[0]))
    transmission_time.append(float(s[1]))
    period.append(int(s[2]))

r = 0.9999

origin_i = 0
origin_j = 0

T = 10000

init_val, not_schedulable = calculate(n, transmission_time, period)
if not_schedulable:
    print("Not schedulable of init state!")
    exit(1)

s = Solution(transmission_time, period, init_val)
s_best = s
benchmark = deepcopy(s)
# T = 1
while T > 1:
    s_cur_value, not_schedulable = calculate(n, transmission_time, period)
    if not_schedulable:
        swap(transmission_time, period, origin_i, origin_j)
        origin_i, origin_j = swap(transmission_time, period)
        continue
    else:
        s_cur = Solution(transmission_time, period, s_cur_value)
        T = T*r
    delta = s_cur.value - s.value
    if s_cur.value < s_best.value:
        s_best = s_cur
    if delta <= 0:
        s = s_cur
    else:
        if random() <= pow(e, -1 * delta / T):
            s = s_cur
    origin_i, origin_j = swap(transmission_time, period)
    end_time = time()
    if end_time - start_time > 14.5: # if run over 14.5 seconds then break
        break

is_arrange = [False] * n

for i in range(n):
    tran, p = benchmark.transmission_time[i], benchmark.period[i]
    for j in range(n):
        if is_arrange[j] == False and s_best.transmission_time[j] == tran and s_best.period[j] == p:
            print(j)
            is_arrange[j] = True
            break
result = calculate(n, s_best.transmission_time, s_best.period)
print(result[0])