No Overlap constraint modeling in MIP

[ArmoredFlash]

Hi,

I'm trying job-shop. 

Representation of Data is as Follows: [Time Start(minutes_of_day),Time Duration(minutes)] .Here Time Start depicts time that is 0 considered as first minute of day(00:00) and so on and Time Duration is duration of task from time it starts so [0,5] means task will start at 0th minute of day that is at 00:00 and will end at 00:05.

I have n-number of machines which only works 30 minutes max a day and when their run time starts when they start first task assigned to them, One machine can continue for 14 minutes at stretch and then needs 3 minutes cooldown break minimum. 14 minutes is a limit and machine can not exceed 14 minutes. But since we have discrete tasks we need to assign multiple tasks in continuation and for that I need arc which store tasks assigned to machine and check for cumulative duration of these tasks as total duration should not exceed 14 minutes. For cooldown assignment, if say we assign two tasks in an arc that totals to 10 minutes, we'll give cooldown after both tasks end and next set of tasks will be assigned after minimum of 3 minutes, this cooldown timer can extend to any length/duration but 3 is minimum.

I'm facing few problems:

• I'm unable to model constraint that tasks are assigned to machine in no-overlap fashion that too in continuous manner(ie one after another)
• I'm unable to incorporate cooldown period.
• I've made bins equalling to number of tasks and finding minimum bins to be used,but  solver.Add((x[b,d] * data[d][0] ) >= bins[b][0] gives no solution whereas  solver.Add((x[b,d] * data[d][0] ) <= bins[b][0] gives solution, this is implemented to assign tasks to bin within active state of bin.

Any help would be much appreciated..!

Here's code I tried which is working but not modelled as per requirements.

 

from ortools.linear_solver import pywraplp

# Creates the model.

model = cp_model.CpModel()

data =[[0,5],

    [0,4],

    [1,6],

    [2,4],

    [3,6],

    [3,2],

    [4,5],

    [5,5],

    [6,4],

    [7,3],

    [8,2],

    [8,3],

    [9,5],

    [10,3]]

# Create the mip solver with the SCIP backend.

solver = pywraplp.Solver.CreateSolver('SCIP')

    

# Creates the variables

i=0

bins = []

total = 0

binused = 0

for d in data:

    bins.append([d[0],d[0]+30])

    i=i+1

    

# Variables

# x[b, d] = 1 if item d is packed in bin b.

x = {}

for b in range(len(bins)):

    for d in range(len(data)):

        x[(b, d)] = solver.IntVar(0, 1, 'x_%i_%i' % (b, d))

        

# y[b] = 1 if bin b is used.

y = {}

for b in range(len(bins)):

    y[b] = solver.IntVar(0, 1, 'y[%i]' % b)

    

# Constraints

# Each item must be in exactly one bin.

for d in range(len(data)):

    solver.Add(sum(x[b, d] for b in range(len(bins))) == 1)

# The amount packed in each bin cannot exceed its capacity.

for b in range(len(bins)):

    solver.Add(

        sum(x[(b, d)] * data[d][1] for d in range(len(data))) <= y[b] *

        14)

    

for b in range(len(bins)):

    for d in range(len(data)):

        solver.Add((x[b,d] * data[d][0] ) >= bins[b][0]  )

#         solver.Add(x[b,d] * data[d][0]  <= bins[b][1]  )

    

# Objective: minimize the number of bins used.

solver.Minimize(solver.Sum([y[b] for b in range(len(bins))]))

status = solver.Solve()

if (status == pywraplp.Solver.OPTIMAL) | (status == pywraplp.Solver.FEASIBLE)  :

    num_bins = 0

    for b in range(len(bins)):

        if y[b].solution_value() == 1:

            bin_items = []

            bin_weight = 0

            for d in range(len(data)):

                if x[b, d].solution_value() > 0:

                    bin_items.append(data[d])

                    bin_weight += data[d][1]

            if bin_weight > 0:

                num_bins += 1

                print('Bin number', b)

                print('Bin',bins[b])

                print('  Items packed:', bin_items)

                print('  Total weight:', bin_weight)

                print()

    print()

    print('Number of bins used:', num_bins)

    print('Time = ', solver.WallTime(), ' milliseconds')

else:

    print(status)

    print('The problem does not have an optimal solution.')

[Laurent Perron]

Tout are mixing two different solvers. 

Ignore scip, use CP-SAT and the CpModel class. Look at the various scheduling examples. 

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/0c857b5a-313f-4508-a25f-2fd517594c2fn%40googlegroups.com.

[ArmoredFlash]

Hi Laurent,

I'm starting with https://github.com/google/or-tools/blob/stable/examples/notebook/examples/gate_scheduling_sat.ipynb as reference.

I got two problems if you could please help me with:

• Firstly, how can we implement this in time domain like not just duration of task but for ex bin that starts at 13:00 and is active till 13:30 so how can we assign tasks to it.
• Secondly, cooldown, for ex after continuous no overlap tasks machine needs to be cooled down to start working on next pair of tasks(this happens within 13:00-13:30 range itself)

Thanks..!

Hope you having great day :)

[Laurent Perron]

1) the solver is based on integer. You need to manage the conversion HH:MM -> some integer value. 

2) look at the jobshop_ft06_distance.py or this one: https://github.com/google/or-tools/blob/stable/examples/python/single_machine_scheduling_with_setup_release_due_dates_sat.py

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/a6ee1e14-9bac-4a1f-b1dd-71ce33a15b75n%40googlegroups.com.