Hello I am trying to identify what could be the name of the following problem:

Let \(I\) be a set of items.

Let \(D\) be a set of defects.

Let \(l_i\) be the length of item \(i \in I\).

Let \(l_d\) be the length of defect \( d \in D\).

Let \(s_d\) be the start position of defect \( d \in D \)

Let \(c_{i,d}\) be a Boolean indicating if an item is compatible with a given defect.

Let L be the length of the material, that has defects, on which the items must be positioned. An item cannot be put on a position where it would intersect with an incompatible defect. The problem being to determine, if it exists a solution where no two items overlaps and where the compatibility with the defects is respected.

If I am considering that all lengths are integer, a possible formulation could be the following:

Let \( x_{i,j} \) be a binary variable indicating if the left of item \(i\) is positioned j units of measure away from the left of the start of the material. I'll consider that variable that would imply putting an item on an incompatible defects are already fixed to 0.

Then the constraints are.

\( \sum_{j \in [0,L]} x_{i,j} = 1, \forall i \in I \)

\( x_{i,j} + x_{i',j'} \leq 1, \forall i \in I, i' \in I, j \in [0,L], j' \in [j,j+l_i] \)

I have already tried to give a look to packing problems with defects, but could not really find something related to the 1 dimensional case, any pointers about what the name of this problem (or a similar problem) could be are welcome.

asked 26 Jun '15, 03:00

Renaud's gravatar image

Renaud
60517
accept rate: 8%

edited 26 Jun '15, 03:01


Sounds to me like a resource-constrained scheduling problem, where items are activities, length means duration, defects are already-scheduled activities, and incompatibility means the two activities share a resource and hence cannot be scheduled simultaneously. In particular, you can enforce the "no two items overlap" constraint by adding a common resource to all the activities in \(I\).

If you choose to solve this with an explicit formulation that uses your \(x\) variables, you might consider replacing your conflict constraints with a clique constraint for each time period: \(\sum_{i \in I} \sum_{j=t-l_i}^t x_{i,j} \le 1, \forall t \in [0,L]\)

link

answered 26 Jun '15, 17:44

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

edited 26 Jun '15, 17:47

Interesting I did not thought of it as a scheduling constraint :-) I'll definitely look in this area for interesting ideas. Thanks for the advice about having one clique constraint per time period, but I am not planning to solve the problem using an explicit formulation.

(27 Jun '15, 14:07) Renaud
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×2
×1
×1

Asked: 26 Jun '15, 03:00

Seen: 582 times

Last updated: 27 Jun '15, 14:07

OR-Exchange! Your site for questions, answers, and announcements about operations research.