How to solve this generalized set packing problem?

Question

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

Answer 1

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