CODEWITHSUNDEEP
algorithmgraph-theoryschedulingjob-schedulingconstraint-satisfaction
user3903448
user3903448

Reputation: 330

Find optimal schedule, given duration & time window for tasks that can be split into sub-tasks

I’m trying to solve, as much as I can, a challenging real world problem where I want to find a schedule that achieves all the tasks without violating the window constraints.

A challenging part is that the task can be split in different blocks too. Those blocks have constraints on sizes though.

A task has -

  1. Duration required to complete it
  2. The minimum and maximum size of a time block in which it can be split
  3. Window in which it should be started and finished. E.g. a task X requires 2 hours and should be completed within July 15 and July 22.

Other things I want to optimize on -

  1. Any particular day should have minimal number of context switches.
  2. A task should be split in minimal number of fragments.
  3. When a new task is added, the existing schedule should change minimally.

Earliest deadline first is one reasonable way which may not be optimal in my opinion.

The input will be one task at a time and hence schedule may change with every additional task.

Another constraints that can make it even more complex is that task can have a score indicating how fulfilling it is and the schedule should maximize the minimum fulfillment score for the day.

I’m sure I’m not the first one to think of this problem, but I’m not yet able to find the precise algorithm for this. Most job scheduling or calendar scheduling algorithms I saw don’t have the concept of splitting a task in time blocks and I think that’s the most challenging part.

This is something that I never came across in text books or any competitive programming websites like topcoder, code forces, or Leetcode.

Upvotes: -2

Views: 513

Answers (1)

ravenspoint
ravenspoint

Reputation: 20457

Since the tasks are added sequentially and moving previously scheduled tasks is disallowed, a globally optimized schedule cannot be obtained.

The best approach, therefore, is to schedule tasks as they arrive so that the amount of flexibility in scheduling the later tasks is maximized. To do this, the fragmentation of free, unscheduled time into smaller and smaller chunks has to be avoided as much as possible. This can be done by scheduling each task into the smallest free chunk in the task window that it will fit.

For example:

Adding  task:a duration 2 windowstarthour:7 windowendhour:12 
task a scheduled at hour 7 on day 0
_______BB___

Adding  task:b duration 2 windowstarthour:0 windowendhour:12
task a scheduled at hour 7 on day 0
task b scheduled at hour 9 on day 0
_______BBBB_

Notice that the second task is NOT scheduled on hour 0, the naïve approach that reduces the longest free chunk from 7 hours to 5, but instead on hour 9 which leaves the longest free chunk available for later, perhaps longer tasks that may then avoid the necessity of being split i.e. reducing the number of 'context switches'.

Now continue with a long duration task that has to be split

Adding  task:x duration 40 windowstarthour:0 windowendhour:50
no single space big enough for task
splitting task
task a scheduled at hour 7 on day 0
task b scheduled at hour 9 on day 0
task x-1 scheduled at hour 0 on day 0
task x-2 scheduled at hour 11 on day 0
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB____

The C++ code for a complete application that implements this algorithm is available at https://github.com/JamesBremner/so76645807WindowTask

Here is the complete output from the application for a test run:

Adding  task:a duration 2 windowstarthour:7 windowendhour:12 
task a scheduled at hour 7 on day 0
_______BB_________________________________________
Day: 0 ContextSwitches: 0 Fulfillment: 15
Day: 1 ContextSwitches: 0 Fulfillment: 0
Day: 2 ContextSwitches: 0 Fulfillment: 0

Adding  task:b duration 2 windowstarthour:0 windowendhour:12
task a scheduled at hour 7 on day 0
task b scheduled at hour 9 on day 0
_______BBBB_______________________________________
Day: 0 ContextSwitches: 1 Fulfillment: 14
Day: 1 ContextSwitches: 0 Fulfillment: 0
Day: 2 ContextSwitches: 0 Fulfillment: 0

Adding  task:x duration 40 windowstarthour:0 windowendhour:50 
no single space big enough for task
splitting task
task a scheduled at hour 7 on day 0
task b scheduled at hour 9 on day 0
task x-1 scheduled at hour 0 on day 0
task x-2 scheduled at hour 11 on day 0
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB____
Day: 0 ContextSwitches: 3 Fulfillment: 2
Day: 1 ContextSwitches: 0 Fulfillment: 0
Day: 2 ContextSwitches: 0 Fulfillment: 0

Adding  task:ff duration 10 windowstarthour:0 windowendhour:50
no single space big enough for task
I can bump tasks with lower fulfillment scores
Day: 0 ContextSwitches: 3 Fulfillment: 2
Day: 1 ContextSwitches: 0 Fulfillment: 0
Day: 2 ContextSwitches: 0 Fulfillment: 0
PS C:\Users\James\code\so76645807WindowTask>

PROPOSAL

Lower fulfillment tasks can be bumped to schedule a new task with higher fulfillment score when all of:

  • normal scheduling and task splitting fails to schedule the new task
  • the bumped tasks schedules overlap the new task window
  • the total fulfillment score for the entire schedule increases
  • the total context switch count does NOT increase

Upvotes: -1

Related Questions