2
$\begingroup$

Using the CP-SAT Solver:

My Model turns infeasible whenever there is no job available for a machine. Not every job can be built on every machine. Example Situtations:

  • Less jobs than machines
  • No jobs buildable on a specific machine

I have tracked down the problem to be in my circuit constraint. When i remove the AddCircuit, it works fine. But I cant tell where exactly the problem is.

seq_length being an NewIntVar (0,max_sequence,name) to handle the max number of similar products in sequence.

Job n is scheduled on machine m if x[n,m]

for line in all_lines:
            job_starts = [job[0] for job in task_per_line[line]]
            job_ends = [job[1] for job in task_per_line[line]]
            arcs = []
            for j1 in all_orders:
                # Initial arc from the dummy node (0) to a task.
                start_lit = model.NewBoolVar('%i is first job on line %i' % (j1, line))
                arcs.append([0, j1 + 1, start_lit]

                # Final arc from an arc to the dummy node.
                isLast = model.NewBoolVar('%i is last job on line %i' % (j1, line))
                arcs.append([j1 + 1, 0, isLast])

                model.AddImplication(x[j1, line].Not(), start_lit.Not())
                model.AddImplication(x[j1, line].Not(), isLast.Not())
                model.Add(job_starts[j1] == 0).OnlyEnforceIf([start_lit])

                # initializing seq lengths
                model.Add(seq_lengths[j1, line] == 1).OnlyEnforceIf(start_lit)
                for j2 in all_orders:
                    if j1 == j2:
                        arcs.append([j1 + 1, j1 + 1, x[j1, line].Not()])
                        continue
                    lit = model.NewBoolVar('%i follows %i on line %i' % (j2, j1, line))
                    model.AddImplication(lit, x[j1, line])
                    model.AddImplication(lit, x[j2, line])
                    arcs.append([j1 + 1, j2 + 1, lit])
                    model.Add(job_starts[j2] == job_ends[j1] ).OnlyEnforceIf(lit)

                    # Respecting max sequence
                    if same_product:
                        model.Add(seq_lengths[j2, line] == seq_lengths[j1, line] + 1).OnlyEnforceIf(lit)
                    else:
                        model.Add(seq_lengths[j2, line] == 1).OnlyEnforceIf(lit)
           model.AddCircuit(arcs)
$\endgroup$

1 Answer 1

3
$\begingroup$

you need to add a self arc 0 -> 0 with a Boolean variable indicating if the circuit is empty.

For for all tasks, add the implication (circuit is empty => task is not performed).

for line in all_lines:
            job_starts = [job[0] for job in task_per_line[line]]
            job_ends = [job[1] for job in task_per_line[line]]
            arcs = []
            no_tasks = model.NewBoolVar(f'no_tasks in {line}')
            arcs.append([0, 0, no_tasks])
            for j1 in all_orders:
                # Initial arc from the dummy node (0) to a task.
                start_lit = model.NewBoolVar('%i is first job on line %i' % (j1, line))
                arcs.append([0, j1 + 1, start_lit]

                # Final arc from an arc to the dummy node.
                isLast = model.NewBoolVar('%i is last job on line %i' % (j1, line))
                arcs.append([j1 + 1, 0, isLast])

                model.AddImplication(x[j1, line].Not(), start_lit.Not())
                model.AddImplication(x[j1, line].Not(), isLast.Not())
                model.Add(job_starts[j1] == 0).OnlyEnforceIf([start_lit])

                # link with no_tasks
                model.AddImplication(no_tasks, x[j1, line].Not())

                # initializing seq lengths
                model.Add(seq_lengths[j1, line] == 1).OnlyEnforceIf(start_lit)
                for j2 in all_orders:
                    if j1 == j2:
                        arcs.append([j1 + 1, j1 + 1, x[j1, line].Not()])
                        continue
                    lit = model.NewBoolVar('%i follows %i on line %i' % (j2, j1, line))
                    model.AddImplication(lit, x[j1, line])
                    model.AddImplication(lit, x[j2, line])
                    arcs.append([j1 + 1, j2 + 1, lit])
                    model.Add(job_starts[j2] == job_ends[j1] ).OnlyEnforceIf(lit)

                    # Respecting max sequence
                    if same_product:
                        model.Add(seq_lengths[j2, line] == seq_lengths[j1, line] + 1).OnlyEnforceIf(lit)
                    else:
                        model.Add(seq_lengths[j2, line] == 1).OnlyEnforceIf(lit)
           model.AddCircuit(arcs)
```
$\endgroup$
1
  • $\begingroup$ What would the self arc look like? $\endgroup$
    – cl_cookie
    Sep 7, 2022 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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