I'm trying to create a dynamic programming algorithm to a job scheduling problem. I have a set of n jobs, with each job i having a start time s(i) and finish time f(i). Start is always before finish, and you can have two jobs at the same time. How would I go about creating an algorithm to maximize the amount of time the resource is busy?
-
invert the cost-function.wildplasser– wildplasser2017-10-29 23:28:51 +00:00Commented Oct 29, 2017 at 23:28
-
@wildplasser Sorry but what does that mean?Andrew Raleigh– Andrew Raleigh2017-10-30 00:17:57 +00:00Commented Oct 30, 2017 at 0:17
Add a comment
|
1 Answer
You have to decide on what state to keep track of at each point. One option would be to keep track of the finish times of the currently running jobs, in which case you could compute the maximum possible busy time roughly as follows.
Create a map from a set of finish times to busy time so far. Initialize it to {null set} -> 0.
For each job in increasing order of start time:
- Create a new map and insert into it all of the entries from the old map which have both finish times greater than the current start time.
- For each remaining entry in the old map remove from the set of finish times those that are less than or equal to the start time of the current job. If the new map does not have an entry for that set of finish times, or if the value associated with the entry in the old map is greater than the value in the new map for that set, insert the resulting entry into the new map. Now insert the finish time for the current job into the set and add to its value the time taken by the new job. If the new map does not have an entry for the resulting set of finish times, or if that entry has a lower value than the value just calculated, add an entry for that set and value to the new map.
- The new map becomes the old map
At the end the largest value in the map is the largest possible busy time. If you keep backtracking information I haven't mentioned, you can trace back to find out what the selection of jobs was.
