[Python / JSP] Splitting tasks in available time windows

[Flemming Jensen]

Hi Everyone!

TL;DR below quote

I'm working on a project with the Job Shop Scheduling and have achieved a schedule that I want to improve upon. The challenge is that I want to split tasks in the available time windows.

I have been through various other posts #1223, #1798

What seems to be the best option is as Laurent described in;
https://groups.google.com/forum/?hl=en#!searchin/or-tools-discuss/FlexibleJobShop$20with$20Machine$20Calendars%7Csort:date/or-tools-discuss/DA_4Pniwhn8/BH2vO5K1BgAJ

So, 

back to the initial method

Let's get a granularity 1 time unit = 1 day, scheduling over 3 weeks, with week-end, and 1 day off (Thu of the second week)

My task has a duration of 4

total duration =  ( I use X to indicate impossible)

M T W T F S S M T W T F S S M T W T F S S

4 4 6 6 6 X X 5 7 7 X 6 X X 4 4 X X X X X

I have duration = 4 when start in [0..1] U [14..15]

I have duration = 5 when start in [7..7]

I have duration = 6 when start in [2..4] U [11..11]

I have duration = 7 when start in [8..9]

I have duration = X when start in [5..6] U [10..10] U [12..13] U [16..20]

And the domain of start is [0..4] U [7..9] U [11..11] U [14..15] (complement of X)

Now I can create my interval variables  (in python for the example)

# Create variables

start = model.NewEnumeratedIntVar([0, 4, 7, 9, 11, 11, 14, 15], 'start')

duration = model.NewIntVar(4, 7, 'duration')

end = model.NewIntVar(0, 20, 'end')  # We can compute it exactly.

# Create indicators

d4 = model.NewBoolVar('d4')

d5 = model.NewBoolVar('d5')

d6 = model.NewBoolVar('d6')

d7 = model.NewBoolVar('d7')

# Link start to indicators

model.AddLinearConstraintWithBounds([(start, 1)], [0, 1, 14, 15]).OnlyEnforceIf(d4)

model.Add(start == 7).OnlyEnforceIf(d5)

model.AddLinearConstraintWithBounds([(start, 1)], [2, 4, 11, 11]).OnlyEnforceIf(d6)

model.AddLinearConstraintWithBounds([(start, 1)], [8, 9]).OnlyEnforceIf(d7)

# Exactly one indicator is true

model.Add(d4 + d5 + d6 + d7  == 1)

# Indicators constraint the duration

model.Add(duration == 4).OnlyEnforceIf(d4)

model.Add(duration == 5).OnlyEnforceIf(d5)
model.Add(duration == 6).OnlyEnforceIf(d6)
model.Add(duration == 7).OnlyEnforceIf(d7)

This way, you are completely flexible.

_________________________________________________

I'm trying to implement the above in my schedule.

I have managed to implement the START-variable with .NewIntVarFromDomain, however now I'm struggling with the duration - anyone can share a thought of how to scale the above?

For each machine (60 in total) I have roughly ~15 different durations ranging from 1 - 32 hours and 40 intervals within a range of 0 - 2182 (unit = hours). 

I have tried to make a loop to identify the duration of each hour (1 - 2182) but without any luck. I could imagine someone has solved this issue before?

[Flemming Jensen]

For those curious, you can see my schedule below (grey areas marks machine downtime implemented according to examples/python/jobshop_with_maintenance_sat.py)

To the far top-right corner you can see the issue as these durations exceeds the time-windows and are therefore implemented at the far end where I haven't limited the capacity.

[Flemming Jensen]

I tried to implement the above without any luck. It is simply too time-consuming to calculate all the durations the way I've tried...

Currently, I have made the start_var + end_var  using the cp_model.Domain.FromIntervals, so I no longer need to add the "maintenance" times to model.AddNoOverlap.

I'm trying to figure out how to add the durations so that they are no longer fixed, but also have boundaries to limit the search space.

Any help would be highly appreciated.

[Flemming Jensen]

I have tried to follow the approach shown by Laurent Perron at this post (splitting tasks). Since my breaks are either 8, 12, 16 or 24 hours I have chosen to split my tasks into intervals of 4, i.e. a task of 26 hours is broken down to 6 x 4 hours + 1 x 2 hours. The good thing is that it's capable of doing a much more "packed" schedule, the bad thing is that it sometimes breaks the chain of intervals for an order with another one so that they get mixed. Does anyone have an idea how to fix it? Please see the image for reference. 

I can also upload code in Python, should it be necessary.

[Alex Dunfee]

Perhaps not the most efficient way, but I have successfully addressed this issue by adding an additional term to the objective function. I have been able to Minimize(sum_of_job_durations) where each job_duration = first_task_in_job.start - last_task_in_job.end. 

You probably have to do some coefficient balancing, but this has worked well for me.

[Flemming Jensen]

Hi Alex,

Thanks for your reply.

I've tried with the below and it seems to be working. However the runtime have gone up quite a bit. Could you elaborate on the coefficient balancing?

Minimize(sum(all_jobs[job_id].end - all_jobs[job_id].start for job_id, job in enumerate(Job_Operation))

BR. Flemming

[Alex Dunfee]

Not sure on what order of magnitude the runtime has increased, so not sure exactly what to suggest, but in order to balance your minimization, you would need to apply weighting to the different terms. Essentially, when you're trying to minimize both the overall makespan of the schedule, and also group all the tasks within an individual jobs close together (what you just implemented) you might end up with competing objective functions. So lets say you have the following

job_durations = []

for job_id, job in enumerate(Job_Operation):

    job_duration = model.NewIntVar(0, horizon, f'job_duration_{job_id}')

    model.Add(job_duration == all_jobs[job_id].end - all_jobs[job_id].start)

    job_durations.append(job_duration)

Minimize((80 * makespan) + (20 * sum(job_durations))

One of the reasons I prefer to make individual variables to track each of the job durations is for illustrative purposes and plotting the improvement in objective values in intermediate solutions. But, as you can see, applying different weights to these terms should have the solver prioritize solutions reducing the makespan a bit more than the job_durations.  

If you don't follow what I mean feel free to post some code so I can see your variables and fit suggestion to them. 

[Flemming Jensen]

Hi Alex, 

Thanks for taking the time! 

Until now I haven't achieved a solution within 30min. I will try to adjust the balancing :-) 

Notes:

1) There are 1000 sales orders (typically of 2-4 jobs)

2) There are 450 jobs (For many sales orders are the same in-going jobs) - i.e. jobs may serve multiple sales orders

4) Sometimes I use "try/except" since a job may not be in both the job file and order file that I have and thus throw an error.

3) I try an objective function consisting of (a) makespan, (b) on-time delivery and (c) job duration

Decision Variables

task_type = collections.namedtuple('task_type', 'start end interval')

job_type = collections.namedtuple('job_type', 'start end')

tard_type = collections.namedtuple('order_type', 'tard ind')

all_tasks = {}

all_jobs = {}

all_orders = {}

machine_to_intervals = collections.defaultdict(list)

#Integer/Bool varaible for tardiness

for sales_id, sales_order in enumerate(dates):

    suffix = '_%i' % (sales_order[0])    

    tard_time = model.NewIntVar(-horizon, horizon, 'tard_time_index' + suffix)

    tard_indicator = model.NewBoolVar('tard_indicator_index' + suffix)

    all_orders[sales_id] = tard_type(tard = tard_time, ind=tard_indicator)

#Integer variable for job end

for job_id, job in enumerate(Job_Operation):

    suffix = '_%i' % (job[0])

    start_var = model.NewIntVar(0, horizon, 'start' + suffix)

    end_var = model.NewIntVar(0, horizon, 'end' + suffix)

    all_jobs[job_id] = job_type(start=start_var, end=end_var)

#Integer variable for operation start, duration and end

for job_id, job in enumerate(Job_Operation):

    for task_id, task in enumerate(job[1]):

        machine = task[0]

        duration = task[1].item()

        suffix = '_%i_%s:%i_%i' % (job[0], task[0], task_id, task[1])

        start_var = model.NewIntVar(0, horizon, 'start' + suffix)

        end_var = model.NewIntVar(0, horizon, 'end' + suffix)

        interval_var = model.NewIntervalVar(start_var, duration, end_var, 'interval' + suffix)

        all_tasks[job_id, task_id] = task_type(start=start_var, end=end_var, interval=interval_var)

        machine_to_intervals[machine].append(interval_var)

#Adding unavailable capacity slots.

for machine in capacity:

    suffix = '%s_%s_%s' % (machine[0], machine[4], machine[5])

    machine_to_intervals[machine[0]].append(model.NewIntervalVar(int(machine[1]), int(machine[2]), int(machine[3]), suffix))

Constraints

# Create disjunctive constraint, i.e. no overlapping

for machine in machines:

    model.AddNoOverlap(machine_to_intervals[machine])

    

#Start + end time of job is equal to start + end of last operation

for job_id, job in enumerate(Job_Operation):

    model.Add(all_jobs[job_id].start == all_tasks[job_id, 0].start)

    model.Add(all_jobs[job_id].end == max(all_tasks[job_id, task_id].end for task_id in range(len(job[1]))))

    

# Precedences inside a job

for job_id, job in enumerate(Job_Operation):

    #print(job)

    for task_id in range(len(job[1]) - 1):

        if str(all_tasks[job_id, task_id + 1][0]).split(":", 4)[0] == str(all_tasks[job_id, task_id][0]).split(":", 4)[0]:

            model.Add(all_tasks[job_id, task_id + 1].start >= all_tasks[job_id, task_id].end)

            #print(all_tasks[job_id, task_id + 1].start, ">=", all_tasks[job_id, task_id].end)

        else:

            model.Add(all_tasks[job_id, task_id + 1].start >= 24 + all_tasks[job_id, task_id].end)

            #print(all_tasks[job_id, task_id + 1].start, ">=", 24 + all_tasks[job_id, task_id].end)

            

# Precedences inside a sales order (try/except because some sales orders jobs are not in the load file)

for sales_order in order:

    prev_job = 0

    for job_id, job in enumerate(sales_order[1]):

        index = np.where(job == jobs)

        try:

            if prev_job != 0:

                model.Add(all_jobs[index[0][0]].start >= (prev_job.end + 72))

                #print(sales_order, all_jobs[index[0][0]].start, ">=", (prev_job.end + 72))

            prev_job = all_jobs[index[0][0]]

        except:

            pass

# Calculate tardiness of jobs and a binary indicator

for sales_id, sales_order in enumerate(dates):

    index = np.where(sales_order[0] == jobs)

    try:

        model.Add(all_orders[sales_id].tard >= all_jobs[index[0][0]].end - dates[sales_id][1])

        #print(all_orders[sales_id].tard >= all_jobs[index[0][0]].end - dates[sales_id][1])

        model.Add(all_orders[sales_id].tard - all_orders[sales_id].ind * horizon <= 0)

    except:

        pass

Objective function

makespan = model.NewIntVar(0, horizon, 'makespan')

model.AddMaxEquality(makespan, [all_jobs[job_id].end for job_id, job in enumerate(Job_Operation)])

job_durations = []

for job_id, job in enumerate(Job_Operation):

    job_duration = model.NewIntVar(0, horizon, f'job_duration_{job_id}')

    model.Add(job_duration == all_jobs[job_id].end - all_jobs[job_id].start)

    job_durations.append(job_duration)

    

tards = []    

for sales_id, sales_order in enumerate(dates):

    tards.append(all_orders[sales_id].ind)

    

model.Minimize((50 * makespan) + (35 * sum(tards)) + (15 * sum(job_durations)))

Solver

# Solve model.

start = time.time()

solution_printer = SolutionPrinter()

solver.parameters.num_search_workers = 8

solver.parameters.max_time_in_seconds = 3600.0

status = solver.SolveWithSolutionCallback(model, solution_printer)

end = time.time()

hours, rem = divmod(end-start, 3600)

minutes, seconds = divmod(rem, 60)

print("{:0>2}:{:0>2}:{:05.2f}".format(int(hours),int(minutes),seconds))

Best regards!

[Alex Dunfee]

Hey,

Sorry it has taken me a while to look into this. Can you explain the logic behind your tardiness calculation? I'm not entirely sure why your constraint defines it as >= as opposed to ==. You're trying to set the tard value as an integer (the result of all_jobs[index[0][0]].end - dates[sales_id][1]) rather than say that the tard "can take on any value greater than all_jobs[index[0][0]].end - dates[sales_id][1]. 

Give that a shot. Hopefully I understood your intent.