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