Semi-Flexible Job Shop Scheduling Problem (SFJSSP) with Machine Shifts and Changeovers

[hpswalters]

I have developed a solution for the SFJSSP with Machine Breaks that works but does not scale well. One of the main reasons for this is that I use machine intervals over the horizon to define the "off-shift" periods; loop through task_duration in hourly intervals and for each hour specify two variables--it looks like this:

for hour in range(task_duration):
  l_hourly_start = model.NewIntVar(0, horizon, f"{alt_suffix}, hour {hour}")
  l_hourly_interval = model.new_optional_fixed_size_interval_var(l_hourly_start, 1, route_presence, f"interval {hour} of {task[alt_id][0]} for {alt_suffix}", )

. These intervals are stored along with the machine off-shift intervals so that the NoOverlap[intervals] can work its magic. What is good about this is:

1. it works
2. I have maximum flexibility with the machines to set shift schedules

What is bad about this is it doesn't scale well with:

1. the number of jobs, routes, and tasks
2. the time increment - most scheduling activities require granularity down to 10 to 15 minutes. This would increase the the number of intervals 4x to 6x.

In attempting to solve this, it occurs to me that a task needs to be broken down into, at most, two parts (assuming all tasks are no longer than shift_duration +1_hour. Therefore, there is either sufficient time on a shift to complete the task (sufficient_time) or there is not (sufficient_time.Not()).

Knowing this, the issue now becomes joining the route_presence and sufficient_shift_time booleans into a structure that permits [route_presence and sufficient_shift_time] or [route_presence and sufficinet_shift_time.Not()]. Another advantage is that I can leverage "new_optional_fixed_size_interval_var" when there is sufficient shift time but two new_optional_interval_var when there is insufficient shift time.

Here is a code snip from the program

if machines[task[alt_id][1]]["avail"] == 24: # Don't need to do this if the machine is avail 24 hrs
    # no need for parts
    starts_per_machines[task[alt_id][1]].append(l_start)
    l_interval = model.new_optional_fixed_size_interval_var(l_start,task[alt_id][0],route_presence,"interval" + alt_suffix,)
    intervals_per_machines[task[alt_id][1]].append(l_interval)
    model.Add(l_start + task[alt_id][0] == l_end).OnlyEnforceIf(route_presence)
    
else: # this is where things get tricky
    # Declare variables to hold some key values
    shift_duration = machines[task[alt_id][1]]["avail"]
    task_duration = task[alt_id][0]  # Ensure duration is defined
    dark_duration = 24 - shift_duration
    start_of_shift = machines[task[alt_id][1]]["daily_start"]
    end_of_shift = start_of_shift + shift_duration

    # Define key boolean variables
    sufficient_shift_time = model.NewBoolVar("sufficient_shift_time" + alt_suffix)
    combined_presence_and_sufficient_shift = model.NewBoolVar("combined_presence_and_sufficient_shift" + alt_suffix)
    combined_presence_and_insufficient_shift = model.NewBoolVar("combined_presence_and_insufficient_shift" + alt_suffix)

    # Define combined boolean variables

    model.AddBoolOr([sufficient_shift_time.Not(), route_presence.Not(), combined_presence_and_sufficient_shift])
    model.AddImplication(combined_presence_and_sufficient_shift, sufficient_shift_time)
    model.AddImplication(combined_presence_and_sufficient_shift, route_presence)  

    model.AddBoolOr([sufficient_shift_time, route_presence.Not(), combined_presence_and_insufficient_shift])
    model.AddImplication(combined_presence_and_insufficient_shift, sufficient_shift_time.Not())
    model.AddImplication(combined_presence_and_insufficient_shift, route_presence)  
    
    # define some basic implications - not sure if this helps or hurts - doesn't really seem to impact solution time

    model.AddImplication(route_presence.Not(), combined_presence_and_insufficient_shift.Not())
    model.AddImplication(route_presence.Not(), combined_presence_and_sufficient_shift.Not())

    model.AddImplication(sufficient_shift_time, combined_presence_and_insufficient_shift.Not())
    model.AddImplication(sufficient_shift_time.Not(), combined_presence_and_sufficient_shift.Not())

    #  Add a few more -- not sure if this helps or hurts - doesn't really seem to impact solution time
    model.Add(combined_presence_and_sufficient_shift + combined_presence_and_insufficient_shift == 1).OnlyEnforceIf(route_presence)
    model.Add(combined_presence_and_sufficient_shift + combined_presence_and_insufficient_shift <= 1)
    
    # Since there are only two parts, we can just loop through them
    for part in range(2): # because there are only two parts
        if part == 0:
            l_part_start = model.NewIntVar(0, horizon, f"{alt_suffix}, part_{part}_start")
            task_hour_start = model.NewIntVar(0, 23,  f"{alt_suffix}, part_{part}_start_hour")
            task_day_start = model.NewIntVar(0, horizon_days,  f"{alt_suffix}, part_{part}_start_day")

            # No matter what, if the route is present, the start of the first part must be the start of the task
            model.Add(l_part_start == l_start).OnlyEnforceIf(route_presence)
            starts_per_machines[task[alt_id][1]].append(l_part_start)


            model.AddModuloEquality(task_hour_start, l_part_start, 24)
            model.AddDivisionEquality(task_day_start, l_part_start, 24)
            
           # define the conditions for sufficient shift time
            model.Add(task_hour_start + task_duration <= end_of_shift).OnlyEnforceIf([sufficient_shift_time])   # route_presence
            model.Add(task_hour_start + task_duration > end_of_shift).OnlyEnforceIf([sufficient_shift_time.Not()]) # route_presence


            #The duration for the first part must be at least 1 hour and will be no longer than the task duration
            l_part_duration = model.NewIntVar(1,task_duration, f"{alt_suffix}, part {part} duration")   

            model.Add(l_part_duration == task_duration).OnlyEnforceIf([combined_presence_and_sufficient_shift]) 
            model.Add(l_part_duration == end_of_shift - task_hour_start).OnlyEnforceIf([combined_presence_and_insufficient_shift])

            l_part_end = model.NewIntVar(0, horizon, f"{alt_suffix}, part {part} end")

            model.Add(l_part_end == l_part_start + l_part_duration).OnlyEnforceIf([combined_presence_and_sufficient_shift])
            model.Add(l_part_end == (task_day_start) * 24 + end_of_shift).OnlyEnforceIf([combined_presence_and_insufficient_shift])

            l_part_interval_insuff = model.new_optional_interval_var(l_part_start, l_part_duration, l_part_end, combined_presence_and_insufficient_shift, f"{alt_suffix}, part {part} interval_insuff",)
            l_part_interval_suff = model.new_optional_fixed_size_interval_var(l_part_start, task_duration, combined_presence_and_sufficient_shift, f"{alt_suffix}, part {part} interval_suff",)

            prior_part_end = model.NewIntVar(0, horizon, f"{alt_suffix}, prior_part_end")
            prior_part_duration = model.NewIntVar(1,task_duration, f"{alt_suffix}, prior_part_duration")   

            model.Add(prior_part_end == l_part_end).OnlyEnforceIf([route_presence])
            model.Add(prior_part_duration == l_part_duration).OnlyEnforceIf([route_presence])
            model.Add(prior_part_end == l_end).OnlyEnforceIf([combined_presence_and_sufficient_shift])  

            intervals_per_machines[task[alt_id][1]].append(l_part_interval_suff)
            intervals_per_machines[task[alt_id][1]].append(l_part_interval_insuff)

        else: #this is only need for the case of insufficient shift time
            # in one of my iterations I created a "0" length interval that started and ended at prior_part_end.  
            # this did not seem to have an impact, so I eliminated it
            l_part_start = model.NewIntVar(0, horizon, f"{alt_suffix}, part {part} start")
            l_part_duration = model.NewIntVar(1, task_duration-1, f"{alt_suffix}, part {part} duration")                                       
            l_part_end = model.NewIntVar(0, horizon, f"{alt_suffix}, part {part} end")

            model.Add(l_part_duration == task_duration - prior_part_duration).OnlyEnforceIf([combined_presence_and_insufficient_shift])
            
            #model.Add(l_part_start > prior_part_end).OnlyEnforceIf([combined_presence_and_insufficient_shift])
            model.Add(l_part_start == (task_day_start + 1) * 24 + start_of_shift).OnlyEnforceIf([combined_presence_and_insufficient_shift])
            model.Add(l_part_end >= l_part_start + l_part_duration).OnlyEnforceIf([combined_presence_and_insufficient_shift])

            l_part_interval = model.new_optional_interval_var(l_part_start, l_part_duration, l_part_end, combined_presence_and_insufficient_shift, f"{alt_suffix}, part {part} interval_insuff",)

            intervals_per_machines[task[alt_id][1]].append(l_part_interval)

            model.Add(l_part_end == l_end).OnlyEnforceIf([combined_presence_and_insufficient_shift])    

with the data

I have attempted multiple iterations defining separate cases for sufficient and insufficient using different variable names, different boolean logic structures for the two conditions (route_presence and sufficient_shift_time. Sometimes I get results, sometimes not. but nothing that gets the solution quality as my original model. I feel confident that this can work and is a viable approach to achieve scalability. I am also fairly confident that there is a correct combination of logic and variables -- I just have not found it, so any and all help/insights would be appreciated.

Thanks,
hpsw

P.S. If it helps I can provide the complete original program and the new program with the data sets I am using