Machine Scheduling - Graph Theory

Question

I am making a list of graph theory exercises and I have enclosed in a question that has the following statement:

Machines are given 1, . . . , n and time intervals I1, . . . , In. For each i, an operator must take care of the i machine during the interval Ii. If Ii Ij 6= , the same operator cannot take care of i and j. Which the minimum number of operators sufficient to operate the machinery? Display an example with n 10. For the example, show the graph that models the problem

So what I’ve concluded so far is that it’s a matching problem, only that because the intersection of the time intervals is not provided, in my head the minimum number of employees would be 1 if all the time intervals were exactly the same, but if they were "engaged" Sequentially I would need two that would alternate. Anyway, can anyone give me a light? I think what I’ve thought so far is completely wrong =/

Answer 1

I will owe the pictures, but I will respond as best I can verbatim

You are working with an optimization problem. In the specific case, you want to minimize the number of operators. Obviously an operator can only take care of one machine at a time in this problem.

A classic optimization problem for the smallest possible is that of graph coloring. In this case, to use this schema, we need to map each graph coloring concept in our current problem.

• Vertices:
  Each vertex is a machine. The vertex i represents the machine i
• Rough edges:
  An edge ij means that the machines i and j are connected at the same time. Or more formally, the intersection I_i with I_j is not empty
• Colors:
  Each color is an operator. Since an operator can only operate one machine at a time, two neighboring vertices cannot have the same color.

A very interesting property that comes from these three definitions above is that every click is composed of machines that are active at exactly the same time.

An example of a graph with 10 vertices could be the simplest of all: no intersection between the time intervals, no edges and therefore the minimum color is 1.

It is not said in the question, but these intervals should be contiguous. Which means that if my machine k is on from 10 am to 12 pm, then is only on again at 14h until 16h, this generates some inconsistencies. But of all sorts it could be normalized to adjoining intervals separating k in the machines k_1 and k_2 for the first and second operating interval respectively.

If a more detailed example of a graph with at least 10 vertices is desired, it is necessary to note that this problem does not generate random graphs.

Invalid graph

An invalid graph example would be the following bipartite graph:

1 --- 2
 \   /
  \ /
   x
  / \
 /   \
3 --- 4

For there are no adjoining intervals that will allow me to make this construction of edges.

Let’s try to demonstrate?

The first thing is to know that I_1 and I_3 has no intersection as it has no edge. I will say that I_1 occurs before I_3. I can say that without losing generality.

Then I’ll put the following values:

I_1: [10, 12]
I_3: [14, 16]

I_2 needs to have intersection with I_1 and I_3 simultaneously. Then, a beautiful value for I_2 would be:

I_2: [11, 15]

Now we can only try to create I_4. Just as I_2, by graph I_4 has intersection with both I_1 and I_3. However, I_4 need to have no intersection with I_2. Any value I try to put in for I_4 will clash with these values of I_2, at least their intersection shall be (12, 14). So it is not possible to generate I_4 given these time constraints, so this graph is not applied to the problem of allocating operators to machines.

But if I was working in the group Z mod 4...

I’ll stop this counter-argument right now! We’re trying to model the real world, so this more exotic mathematics there doesn’t apply to machines being turned on at intervals of time. Time follows the principle of good ordering, unlike circular groups... so this argument is invalid for the modeled problem.

Valid graph generation algorithm

I haven’t been able to think of an algorithm to validate whether a graph is valid or not, but I know how to generate a valid graph.

For this algorithm you will need a blank sheet, preferably lined, and a pencil or pen. Set the top of the sheet to "the past", already the bottom as "the future". Separate the sheet into n columns, being n the number of machines desired.

Then, for each column, position the pencil on a staff and, without removing it from the paper, cross to another staff below. This risk made in the column c will be the break I_c. For example, for n = 4:

#
#   #
#   #      #
    #      #
           #
       #   #
       #   #
       #   #
           #

Note that we have here the following intersections:

• machine 1 with machine 2 as both are in times 2 and 3
• machine 1 with machine 2 with machine 4, because the three are in time 3
• machine 3 with machine 4, because the time interval [6, 8] belongs to the intersection I_3 with I_4

With this information of the intersections at hand, we can draw our graph. Is this graph will be valid for modeling our problem.

In the above case, the graph would be the following:

1 --- 2
 \    |
  \   |
   \  |
    \ |
     \|
      4 --- 3

Which by the way needs 3 colors.

Valid graph generation algorithm, v2

Basically it is the most suitable adaptation to a programmatic model, less didactic:

To n any machines, manage n number pairs (A_i,B_i) such that A_i < B_i. These are the operating time intervals of the machines. If there happens to be a non-empty intersection between (A_i,B_i) and (A_j,B_j), then in the graph there must be the edge ij. Detected all intersections, you will have a valid graph of n vertices to this problem of worker allocation by machine

Algorithm to identify invalid graphs

I have no algorithm in mind that makes this detection, so I created the following question: How to identify an invalid graph for operator allocation problem per machine?