Job Sequencing with Deadlines in Every LanguagePublished on 03 November 2018 (Updated: 03 November 2018)
Job sequencing is an optimization problem where the goal is to maximize the profit earned by completing jobs. In this particular rendition of the problem, jobs have both a profit and a deadline, and all jobs can be completed in the same amount of time:
In this example, we have four jobs sorted by largest profit first. Using the greedy method, we can come up with the best sequence by choosing the job with the current highest profit and scheduling it at the last possible moment. In this case, we would end up with the following sequence:
J2, J3, J1
Because the last possible job we can choose has a deadline of 3, we can only select 3 jobs at most for our sequence. As a result, we cannot complete J4. In total, we can make a profit of 50.
Be aware that the output sequence is not unique. There may be multiple configurations that yield the same profit.
In order to implement this program in your choice language, you should define the input interface as follows:
$ ./job-sequencing.lang "25, 15, 10, 5" "3, 1, 2, 2"
In other words, the input routine should accept a list of profits and a list of deadlines. It will be up to the program to verify that these lists are valid.
Once the program has determined a correct sequence, it should output the maximum profit only. For example:
$ ./job-sequencing.lang "25, 15, 10, 5" "3, 1, 2, 2" $ 50
Naturally, this is for testing purposes as verifying all of the possible sequences would be challenging.
The following table contains various test cases that you can use to verify the correctness of your solution:
|No Input||“Usage: please provide a list of profits and a list of deadlines”|
|Empty Input||“Usage: please provide a list of profits and a list of deadlines”|
|Missing Input||“25, 15, 10, 5”||“Usage: please provide a list of profits and a list of deadlines”|
|Sample Input||“25, 15, 10, 5” “3, 1, 2, 2”||50|
|Sample Input||“20, 15, 10, 5, 1” “2, 2, 1, 3, 3”||40|
Currently, there are no articles. If you’d like to begin contributing, head over to the repo to get started.