I'm working on a scheduling optimization problem where we have a set of tasks that need to be completed within a certain timeframe.
Each task has a schedule that specifies a list of time slots when it can be performed. The schedule for each task can be different depending on the weekday.
Here is small sample (reduced number of tasks and time slots):
task_availability_map = {
"T1" : [0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
"T2" : [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
"T3" : [0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
"T4" : [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
"T5" : [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
"T6" : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
"T7" : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0],
"T8" : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0],
"T9" : [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
"T10": [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
}
The constraint is that only up to N tasks can be performed in parallel within the same time slot (if they overlap). The group of parallel tasks always takes the same amount of time regardless of whether 1 or N are being done.
The objective is to minimize the number of time slots.
I've tried a brute force approach that generates all time slot index permutations. For each index in a given permutation, get all tasks that can be scheduled and add them to a list of tasks to be excluded in the next iteration. Once all iterations for a given permutation are completed, add the number of time slots and the combination of indices to a list.
def get_tasks_by_timeslot(timeslot, tasks_to_exclude):
for task in task_availability_map.keys():
if task in tasks_to_exclude:
continue
if task_availability_map[task][timeslot] == 1:
yield task
total_timeslot_count = len(task_availability_map.values()[0]) # 17
timeslot_indices = range(total_timeslot_count)
timeslot_index_permutations = list(itertools.permutations(timeslot_indices))
possible_schedules = []
for timeslot_variation in timeslot_index_permutations:
tasks_already_scheduled = []
current_schedule = []
for t in timeslot_variation:
tasks = list(get_tasks_by_timeslot(t, tasks_already_scheduled))
if len(tasks) == 0:
continue
elif len(tasks) > MAX_PARALLEL_TASKS:
break
tasks_already_scheduled += tasks
current_schedule.append(tasks)
time_slot_count = np.sum([len(t) for t in current_schedule])
possible_schedules.append([time_slot_count, timeslot_variation])
...
Sort possible schedules by number of time slots, and that's the solution. However, this algorithm grows in complexity exponentially with the number of time slots. Given there are hundreds of tasks and hundreds of time slots, I need a different approach.
Someone suggested LP MIP (such as Google OR Tools), but I'm not very familiar with it and am having a hard time formulating the constraints in code. Any help with either LP or some other solution that can help me get started in the right direction is much appreciated (doesn't have to be Python, can even be Excel).
x[i,t]= 1 if task i is assigned to time slot t and 0 otherwise
), and this is easily modeled as a MIP. I don't think a CP has a big advantage here. Brute force (or complete enumeration) looks not very promising to me. – Laze