Алгоритм планирования 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()

Answer 2

Прежде всего, поймите self в Python. Читать ссылка

Во-вторых, понять проблему последовательности работы. Читать ссылка

Затем посмотрите на приведенный ниже код

class Scheduling:

  def schedule(self, n, deadline, jobs):
    # max number of jobs you can schedule is the max deadline available.
    filledJobs = ['dummy']*max(deadline);
    i = 0
    # start assigning the jobs in a greeedy way
    while i < n:
        job = jobs[i]
        j = deadline[i]
        # assign the job from the last deadline
        while j > 0:
            if(filledJobs[j-1] == 'dummy'):
                filledJobs[j-1] = job
                break
            j = j - 1
        i = i + 1

    return filledJobs

def main():
   sins = Scheduling()
   n = 4
   deadline = [1,1,2,2]
   # assuming jobs are sorted w.r.t  profits
   # I represented the jobs with string to be clear
   jobs = ['a', 'b', 'c', 'd']

   sjobs = sins.schedule(n, deadline, jobs)
   print (sjobs)  

if __name__ == "__main__":
  main()