Python 调度算法

Question

我正在编写一个用于测试目的的调度算法，并遵循“算法简介”一书，但这是我所能得到的。截至目前，这项工作正在“某处无限循环”的杂草中消亡。一般来说，该算法应该有利润，我们根据利润对所有其他数组进行排序“但我现在只是忽略它”并且我的输入已经排序。因此，截止日期和通过的作业已经排序。需要一些帮助，因为它仍然无法正常工作。

#!/usr/bin/python3.6

class Scheduling:

  def schedule(self, n, deadline, jobs):
    self.fdeadline = deadline
    self.J = []
    self.J.append(jobs[0])
    self.i = 1
    while self.i <= n:
      self.K = self.J.copy() 
      self.K.append(jobs[self.i]) 
      self.i = self.i + 1
      if self.feasible(self.K, self.fdeadline) == True :
        self.J = self.K

    return self.J  

  def feasible(self, K, fdl):
    self.tmp = K
    self.isFeasible = True

    self.i = 0
    self.j = 1
    self.k = 0 

    while self.i < len(self.tmp):
      while self.j < len(self.tmp):
        self.index1 = self.i
        self.index2 = self.j
        if (fdl[self.index1] > fdl[self.index2]):
          self.tmp[i], self.tmp[j]  =  self.tmp[j], self.tmp[i]  

    while self.k < len(self.tmp):
       self.job  = self.tmp[self.k]
       if (fdl[self.job] < k + 1):
         isFeasible = False
         break

    return isFeasible 


def main():
   sins = Scheduling()
   n = 4
   deadline = [1,1,2,2]
   jobs = [4, 2, 1, 3]
   sjobs = sins.schedule(n, deadline, jobs)
   print (sjobs)  

if __name__ == "__main__":
  main()

Answer 1

这是一个功能齐全的调度代码，它可能需要一些小的改进，但它工作正常。

#!/usr/bin/python3.6

from operator import itemgetter

class Scheduling:
    def __init__(self, jobs):
        self.jobs = jobs

    def schedule(self, n, deadline):
        self.sdl = deadline
        self.J = []
        self.J.append(self.jobs[1])
        self.x = 2
        while self.x < n:
            self.K = self.J.copy()
            self.K.append(self.jobs[self.x])
            self.x = self.x + 1
            self.feasibility = self.feasible(self.K, self.sdl)
            if self.feasibility == True:
                self.J = self.K.copy()

        return self.J

    def feasible(self, K, fdl):
        self.tmp = K
        self.isFeasible = True

        self.i = 0
        self.j = 1
        self.k = 0


        while self.i < len(self.tmp):
            while self.j < len(self.tmp):
                self.index1 = self.jobs.index(self.tmp[self.i])
                self.index2 = self.jobs.index(self.tmp[self.j])
                self.j = self.j + 1
                if (fdl[self.index1] > fdl[self.index2]):
                    self.tmp[self.i], self.tmp[self.j] = self.tmp[self.j], self.tmp[self.i]
            self.i = self.i + 1

        while self.k < len(self.tmp):
            self.job = self.tmp[self.k]
            self.jobindex = self.jobs.index(self.job)
            self.dlineval = fdl[self.jobindex]
            self.ftest = self.k + 1
            self.k = self.k + 1
            if (self.dlineval < self.ftest):
                self.isFeasible = False
                break

        return self.isFeasible

def main():
    n = 7
    jobs =     [0, 1, 2, 3, 4, 5, 6]
    deadline = [0, 2, 4, 3, 3, 2, 1]
    profit =   [0 , 46, 52, 30, 36 ,56, 40]

    midresult = [list(x) for x in zip(deadline, profit ,jobs)]
    midresult.sort(key=lambda k: (k[0], -k[1]))
    deadline, profit, jobs = map(list, zip(*midresult))

    sins = Scheduling(jobs)
    sjobs = sins.schedule(n, deadline)
    print("\n Jobs", sjobs)

    finalprofit = []
    finaldl = []

    for c in range(len(sjobs)):
      item = sjobs[c]
      jobsindex = jobs.index(item)
      finalprofit.append(profit[jobsindex])
      finaldl.append(deadline[jobsindex])

    print("\n profit", finalprofit)
    print("\n Deadline", finaldl)

if __name__ == "__main__":
    main()