Python Scheduling Algorithm

Question

I am writing a scheduling algorithm for testing purposes and following the "Introduction to Algorithm book", but this is as far as I can get. As of now the job is dying in the weed "Endless loop somewhere". Generally, the algorithm should have a profit and we sort all other arrays according to profit "But I am just ignoring that for now" and my inputs are already sorted. So, the deadline and jobs passed are already sorted. Need somehelp as its still not working.

#!/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

Here is a fully functioning code to the scheduling, it might need some small refinements, but its working fine.

#!/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

First of all understand self in python. Read link

Secondly understand the job sequencing problem. Read link

Then, look at the below code

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()