# How to solve this generalized set packing problem?

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

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$$.

• Related question: or.stackexchange.com/questions/8435/….
– prubin
Sep 30, 2022 at 22:03
• What is the objective function?
– prubin
Sep 30, 2022 at 22:04
• @prubin edited my question with objective
– KGM
Sep 30, 2022 at 22:13
• 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)?
– prubin
Oct 1, 2022 at 3:05
• @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.
– KGM
Oct 1, 2022 at 7:56

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.