3
$\begingroup$

I have a machine mapping problem.

There are several machines and several tasks. Tasks are of different types and need different number of machines, such as 2,4 8, etc machines.

Due to machines capability, every task can not be performed by all the machines. Once we assign some machines to a task, the machines should be adjacent.

For example, the 1st task has a demand of 2 machines. The options are machines {1,2} and {5,6} and {9,10} and {13,14} and {17,18} and {21,22}. Note again that the machines mapped to any task must be contiguous.

The tasks and the associated options are given below

Task1: {{1,2},{5,6},{9,10},{13,14},{17,18},{21,22}};

Task2: {{3,4},{7,8},{11,12},{15,16},{19,20},{23,24}};

Task3: {{1,2,3,4},{13,14,15,16}};

Task4: {{1,2,3,4,5,6,7,8},{17,18,19,20,21,22,23,24}};

Task5: {{1,2,3,4,5,6,7,8},{9,10,11,12,13,14,15,16}};

One machine can be allocated to one task only, i.e., one machine can not be shared by multiple tasks.

The tasks are ordered in terms of their priority. For example, task 1 has higher priority than task 2, task 2 has higher priority than task 3, and so on.

Need to assign machines to as many tasks as possible.

The figure just shows one small instance of a problem.

The optimal mapping is shown here. That is the first task gets assigned with its 2nd option, 2nd task gets assigned with its 2nd option, 3rd task gets assigned with its 1st option and so on.

I am looking for a purely heuristic solution. Does not prefer any meta-heuristic for some reasons. A solution than can be generalized to other similar problem instances.

$\bf{Objective}:$

Each task has one utility value, $u_p, p=1,2,\cdots, P$ where $P$ is the number of tasks. We have $u_1>u_2>u_3>\cdots>u_P$

$u_1=0.9706$, $u_2=0.9572$, $u_3=0.8003$, $u_4=0.4854$, $u_5=0.1576$

The objective is to maximise the sum-utility, $max \sum_{p=1}^Pu_p$.

$\endgroup$
7
  • $\begingroup$ Related question: or.stackexchange.com/questions/8435/…. $\endgroup$
    – prubin
    Sep 30, 2022 at 22:03
  • 1
    $\begingroup$ What is the objective function? $\endgroup$
    – prubin
    Sep 30, 2022 at 22:04
  • $\begingroup$ @prubin edited my question with objective $\endgroup$
    – KGM
    Sep 30, 2022 at 22:13
  • $\begingroup$ So, in the diagram, there is no significance to the numbering of the options? For instance, if we renumbered the options for person 1 in ascending order rather than starting with 5, the optimal solution would remain the same (assign person 1 resources 5 and 6)? $\endgroup$
    – prubin
    Oct 1, 2022 at 3:05
  • $\begingroup$ @prubin we can ignore the significance to the numbering of the options. We can renumber the options for all the persons in ascending order rather in accordance with the resource sets. $\endgroup$
    – KGM
    Oct 1, 2022 at 7:56

1 Answer 1

1
$\begingroup$

You can try a random search heuristic. To begin, enumerate all resource blocks that can be assigned (the 18 colored blocks in your diagram) and calculate which conflict with each other. If we number your blocks 1 to 18 in raster scan order, then block 2 (resources 5 and 6) conflicts with block 15 (resources 1 through 8) etc. Let $N$ be the number of resource blocks (18 here).

Now generate a random permutation $\pi$ of $1,\dots,N$ and go through your list people in descending priority order, assigning each person the available resource block whose index appears earliest in $\pi$ among those compatible with that person. After making an assignment, that block and any conflicting blocks become unavailable (meaning their indices are removed from $\pi$). If none of the remaining blocks are compatible, the person goes unserved.

Once an assignment is complete, check to see if it is a new incumbent (objective value better than the current incumbent), then generate a new permutation and repeat the process. You can run the heuristic for either a fixed number of iterations or a fixed amount of time, and you can exit early if you get a provably optimal solution (everyone got served).

$\endgroup$
2
  • $\begingroup$ Unfortunately, it is not possible to rely on such randomness. Random permutation is fine but doing it like iteratively is not viable for some reasons. Prefer a one shot solution as before. And just to make sure, block 2 also conflicts with block 17, right! Would you please comment on 'Generate a new permutation and repeat the process'. Is it a completely new assignment process and does not depend on the previous assignment? $\endgroup$
    – KGM
    Oct 2, 2022 at 10:55
  • $\begingroup$ Yes, blocks 2 and 17 conflict, and yes, when you generate a new permutation you are starting over (though you do retain the best solution found so far). $\endgroup$
    – prubin
    Oct 2, 2022 at 15:38

Your Answer

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

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