Scheduling Jobs with Deadlines on a Single Machine

# Problem definition.

In scheduling Jobs with deadlines on a single machine we have the machine and N jobs to be processed. Each job must be processed for $$p_{j}$$ time units without interruption, and each job is available for processing at time $$r_{j}$$. Each job have due date $$d_{j}$$ .

If we stop computing job j on time $$c_{j}$$ lateness of job is $$c_{j}-d_{j}$$

The aim is to minimalize maximum lateness.

# Solution

Scheduling Jobs with deadlines on a single machine problem is solved by greedy algorithm.

at each moment that machine is idle, we start procesing next available job with the earliest due date.

# Example

#include <iostream>
#include <utility>
int main() {
// sample data
typedef double Time;
std::vector<Time> time = { 2.1, 3.1, 4.1, 5.1, 6.1, 7.1, 8.1 };
std::vector<Time> release = { 1, 2, 3, 4, 5, 6, 7 };
std::vector<Time> due_date = { -1, 0, -2, -3, -4, -5, -6 };
auto jobs = paal::irange(time.size());
std::vector<std::pair<decltype(jobs)::iterator, Time>> jobs_to_start_dates;
Time delay =
jobs.begin(), jobs.end(), [&](int i) { return time[i]; },
[&](int i) { return release[i]; },
[&](int i) { return due_date[i]; },
back_inserter(jobs_to_start_dates));
for (auto job_start_time : jobs_to_start_dates) {
std::cout << "Job " << (*job_start_time.first)
<< " Start time: " << job_start_time.second << std::endl;
}
// print result
std::cout << "Solution: " << delay << std::endl;
return 0;
}

# Complexity

Complexity of the algorithm is $$O(|N|*log(|N|))$$ where N is size of input

# References

The algorithm analysis is described in [23]