Series

Scheduling Algorithms

You can't be late twice if you're already late 😉


  • Bijon Setyawan Raya

  • July 05, 2022

    12 mins


    You can't be late twice if you're already late 😉

    Scheduling Algorithms (2 Parts)


    I found this algorithm on a book called Handbook of Scheduling: Algorithms, Models, and Performance Analysis, written by James H. Anderson and Joseph Y-T. Leung, which was originally published in 2004.

    In the book, I found several algorithms that are suitable for my experiment such as Kuhn-Munkres and Branch-and-Bound algorithms.

    While reading, I stumbled upon an algorithm called Moore-Hodgson which helps us minimize the number of late jobs given we have too many things to do.

    That algorithm reminds me of my experience in the undergraduate program where most students procrastinate and pill up the work near the due dates.

    I realized the algorithm was not complicated, and I gave it a try to implement it in golang.

    You should know that this implementation is based on one of the slides provided in a class called Sequencing and Scheduling at TU Eindhoven.

    Before we get into the coding part, let's see how this algorithm works.

    Algorithm#

    Let djd_j be the due date of job jj, pjp_j be the processing time of job jj, and CjC_j be the completion time needed to finish the jobs.

    1. Sort the jobs by due date in increasing order.
    2. Let scheduled job set and the rejected job set be empty.
    3. Let the completion time to be Cj=0C_j = 0.
    4. For j=1,,nj = 1, \ldots, n do
      • Add jjj_j to the scheduled job set.
      • If Cj+pjdjC_j + p_j \leq d_j,
        • CjC_j = Cj+pjC_j + p_j.
      • Else
        • Find a job with the largest processing time in the scheduled job set, and let it be dkd_k.
        • Remove the job from the scheduled job set, and move it to the rejected job set.
        • CjC_j = Cj+pjdkC_j + p_j - d_k.
    5. Add the jobs in the rejected job set to the scheduled job set in order of due date.

    Let's say there are several jobs with due dates and their processing times.

    Job12345
    Due Date djd_j678911
    Processing Time pjp_j43256

    Let's add the completion time needed if we plan to do all the jobs.

    Job12345
    Due Date djd_j678911
    Processing Time pjp_j43256
    Completion Time CjC_j4791420

    Clearly, the time needed to finish job 1 and job 2 is 4+3=74+3=7.

    Hence the total completion time for those 5 jobs requires 20 days. Meaning that we can only deliver 2 jobs on time, and 3 jobs late.

    With Moore-Hodgson, we can skip over the tasks that require more processing time and include tasks that require less processing time. Thus, we can maximize the number of jobs that we can deliver.

    Solving the probem above with Moore-Hodgson, we then have the following table.

    Job12345
    Due Date djd_j678911
    Processing Time pjp_j43256Rejected Jobs
    Completion Time CjC_j4-----
    47----
    479---
    47*--Job 3
    47*12-Job 3
    47**-Job 3 & 4
    47**13Job 3 & 4
    47***Job 3, 4, & 5

    Note that the dash symbol - is used to represent a job is not yet added, and the star symbol * is used to represent a job that is rejected.

    Since the result is pretty much the same as we initially assummed, let's try another example with more jobs.

    Job12345678
    Due Date djd_j6891120252835
    Processing Time pjp_j416368710

    Adding the completion time, we have the following output.

    Job12345678
    Due Date djd_j6891120252835
    Processing Time pjp_j416368710
    Completion Time CjC_j45111420283545

    It takes 45 days in order to complete all jobs. Meaning that, we can only deliver 2 jobs, and 6 jobs late. Imagine telling your boss that kind of news.

    Let's see how many jobs we can optimize the numbers of jobs that we can deliver on time. Solving the probem above with Moore-Hodgson, we then have the following table.

    Job12345678
    Due Date djd_j6891120252835
    Processing Time pjp_j416368710Rejected Jobs
    Completion Time CjC_j4--------
    45-------
    4511------
    45*-----Job 3
    45*8----Job 3
    45*8----Job 3
    45*814---Job 3
    45*81422--Job 3
    45*8142229-Job 3
    45*814*29-Job 3 & Job 6
    45*814*2931Job 3 & Job 6

    Note that the dash symbol - is used to represent a job is not yet added, and the star symbol * is used to represent a job that is rejected.

    Hence with the help of the algorithm, we can have 6 jobs delivered on time and 2 jobs late. It doesn't sound bad at all.

    In this project, we will implement this algorithm in golang.

    First, we need a job master to orchestrate all the jobs it's seen.

    type JobMaster struct {
    	initialJobs   []Job
    	scheduledJobs []Job
    	rejectedJobs []Job
    	lastJobID     int
    }
    
    type Job struct {
    	id             int
    	dueDate        int
    	processingTime int
    }
    

    I have two arrays to store jobs. scheduledJobs is where we store the jobs that we intend to do, and rejectedJobs is a list of jobs that we have to sacrifice.

    func main() {
      var master JobMaster
      jobs := [][]int{
          {6, 4},
          {7, 3},
          {8, 2},
          {9, 5},
          {11, 6},
      }
    
      for _, job := range jobs {
          master.AddJob(job[0], job[1])
      }
    
      master.AssignJobs()
    
      scheduledJobs := master.scheduledJobs
      sort.Sort(Jobs(master.rejectedJobs))
    
      endResult := append(scheduledJobs, master.rejectedJobs...)
    
      fmt.Println("Scheduled jobs are", master.scheduledJobs)
      fmt.Println("Remaining jobs are", master.rejectedJobs)
      fmt.Println("All the scheduled jobs are", endResult)
    }
    

    From line 4 to 8, it is a list of jobs that we intend to optimize. The first column indicates the due date, and while the second is the processing time.

    Once a job is added, the job master will immediately assign the job with a unique ID in order to avoid duplicate jobs.

    After all jobs are added, the list of jobs will be passed to a function called AssignJobs() which returns a list of scheduled jobs. This following function is the implementation of Moore-Hodgson algorithm.

    func (self *JobMaster) AssignJobs() []Job {
      // Sort jobs in increasing manner of due date
      sortedJobs := self.initialJobs
      sort.Sort(Jobs(sortedJobs))
    
      var totalCompletionTime int = 0
    
      // Iterate over jobs and append a job accordingly
      for _, job := range sortedJobs {
        self.scheduledJobs = append(self.scheduledJobs, job)
        if totalCompletionTime+job.processingTime <= job.dueDate {
          totalCompletionTime += job.processingTime
        } else {
          var threshold = math.MinInt
          var deleteIndex int
          for index, job := range self.scheduledJobs {
            if job.processingTime > threshold {
              deleteIndex = index
            }
          }
    
          // remove the job with the largest
          // processing time from schedulerJobs
          // and move it to remainingJobs
          for _, job := range self.scheduledJobs {
            if job.id == deleteIndex+1 { // +1 because the job id starts from 1
              self.rejectedJobs = append(self.remainingJobs, job)
              self.scheduledJobs = append(self.scheduledJobs[:deleteIndex], self.scheduledJobs[deleteIndex+1:]...)
            }
          }
        }
      }
      return self.scheduledJobs
    }
    

    After assigning the jobs, we will have a list of scheduled jobs and rejected jobs. Before we append the rejected jobs to the scheduled jobs, we have to sort them in order to make sure that the jobs are in the correct order shown in line 18 in the main function.

    For more details of the code, click here to see this project repository on Github.