I am trying to identify the name of the following problem (in case it has already been studied or similar class of problems otherwise). In order to keep the problem description short I am not trying to get rid of any non-linearity in the constraints. Let us consider a segment of size \(L\), divided in different (non-overlapping) quality zones \(Z\). \(\forall i \in Z: qz_i\) designates the quality of zone \(i\) \(\forall i \in Z: sz_i\) designates the start of zone \(i\) \(\forall i \in Z: ez_i\) designates the end of zone \(i\) We are also given a set S of small segments to be placed on the bigger segment \(\forall j \in S: Q_j\) designates the set of qualities compatible with segment \(j\) \(\forall j \in S: l_j\) designates the length of segment \(j\) The objective is to place all segments of S on the big segment so that no two segments overlap and that a small segment is only intersecting with compatible quality zones on the big segment. \(\forall j \in S: ss_j\) is a variable designating the starting position of segment \(j\) Let \(m\) be the minimum distance between two segments if they do not follow directly each others We then have the following constraints \(\forall j \in S, \forall i \in Z: [ss_j, ss_j + l_j] \cap [sz_i,ez_i] \neq \emptyset \implies qz_i \in Q_j\) \(\forall j,j' \in S: [ss_{j'}, ss_{j'} + l_{j'}] \cap [ss_j, ss_j + l_j] = \emptyset\) \(\forall j,j' \in S: |ss_{j} - (ss_{j'} + l_{j'})| = 0 \) OR \( |ss_{j} - (ss_{j'} + l_{j'})| \geq m \) The objective being to determine whether or not a feasible solution exists. I have the feeling that it might map to some existing scheduling problem but I cannot pin-point it.
asked
Renaud |

Your problem has some similarities to a single machine scheduling problem (mapping master segment to machine, small segments to jobs, and length of segment to processing time). The two major differences are that: (a) you seem to be looking for any feasible solution (whereas machine scheduling problems typically have an objective function, such as makespan or tardiness); and (b) you have restrictions on where a small segment can be put. In machine scheduling, typically there are either no restrictions on when a job starts (other than not overlapping a running job), or there are "release dates" (start a job on or after some point). You might look at constraint programming solutions for machine scheduling. Constraint solvers generally have some form of global non-overlap constraint (such as "disjunctive()" in MiniZinc). Your quality requirements actually simplify a CP model. Assuming that your decision variables include the starting points for each small segment, you can preprocess the problem, removing from the domain of each start variable any positions that would lead the small segment to wander into a zone of insufficient quality. Shrinking variable domains in a CP model is a good thing.
answered
Paul Rubin ♦♦ |