10
$\begingroup$

Context:

I am dealing with a kind of scheduling problem, in which I have a set of tasks and machines. All tasks must be assigned to machines (not necessary all of them). In addition to that, I must calculate the cost of transferring the product between two machines.

For starting, I based my problem in the nurses assignment: https://developers.google.com/optimization/scheduling/employee_scheduling

However, I do not know how to obtain the cost of changing machine, it means, take the material from one machine to another.

To consider the task assignment with the process sequence I established the binary variable X[w, o, j], where w is the machine, o is the operation and j is the position on the process plan.

For calculating the cost of changing machine I also established another binary variable T[w1, w2, j-1, j], that states if there is a material transition from one machine to another in two followed positions on the process plan.

Some code:

# Create the decision variabl
X = {}
for w in range(num_machines):
    for p in range(num_operations):
        for j in range(num_operations):
            X[w, p, j] = model.NewBoolVar('X_{}_{}_{}'.format(w + 1, p + 1, j + 1))
T = {}
for w1 in range(num_machines):
    for w2 in range(num_machines):
        for j in range(1, num_operations):
            #if w1 != w2:
                # T[w1, w2] = model.NewBoolVar(f'T_{w1}_{w2}') # using f-string notation
            T[w1, w2, j-1, j] = model.NewBoolVar('T_{}_{}_{}_{}'.format(w1 + 1, w2 + 1, j, j + 1))

B = model.NewBoolVar('B')     # declaring an intermediate variable

I've tried to implement some constraints:

1) The number of transitions must be equal the number of operations -1
  number_transitions = sum(
        T[(w1, w2, j-1, j)] 
        for w1 in range(num_machines) 
        for w2 in range(num_machines)
        for j in range(1, num_operations)

        )
    model.Add(number_transitions == num_operations - 1)

So to establish the relation between X and T I tried 2 different ways, but any of them worked.

1st way:

# Implementing B == [X1 + X2]
for w1 in all_machines:
    for w2 in all_machines:
        for p1 in all_operations:
            for p2 in all_operations:
                for j in range(1, num_operations):
                    model.Add(X[w1, p1, j-1] + X[w2, p2, j] == 2).OnlyEnforceIf(B)
                    model.Add(X[w1, p1, j-1] + X[w2, p2, j] != 2).OnlyEnforceIf(B.Not())

# Reinforcing the value of T
for w1 in all_machines:
    for w2 in all_machines:
        for j in range(1, num_operations):
            model.Add(T[w1, w2, j-1, j] == 1).OnlyEnforceIf(B)
            model.Add(T[w1, w2, j-1, j] == 0).OnlyEnforceIf(B.Not())

2nd way:

 for p in all_operations:
     for w1 in all_machines:
         for w2 in all_machines:
             for j in range(1, num_operations):
                 model.Add((X[w1, p, j-1] + X[w2, p, j]) == T[w1, w2, j-1, j] + 1)

In both of ways, when I run the code, it returns as result just solutions that do not do transitions between two machines, meaning that these constraints are not being read correctly.

I would like to know if there is a better way to solve this problem by establishing the relation between variables X and T.

I guess that it could be possible to solve like a TSP, but in my case, not all nodes are visited, but just nodes(machines) required to do a task.

Someone know how could I solve this problem? Or maybe do you have an example to send me?

Thanks in advance,

I asked the same question here: https://stackoverflow.com/questions/58709914/tsp-problem-traveller-does-not-visit-all-nodes-google-or-tools

$\endgroup$
  • $\begingroup$ If you do go down the TSP road, you may consider looking into the orienteering problem - it has the flavor of the TSP but not all nodes need to be visited. Here's a survey by Vansteenwegen et al 2011 (doi.org/10.1016/j.ejor.2010.03.045). $\endgroup$ – E. Tucker Nov 5 '19 at 13:46
6
$\begingroup$

(already answered on S.O. )

You should have a look at Jobshop scheduling example with transitions

In particular, it maintains a graph of direct successor between tasks on the same machine.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.