I'm sure this problem has been addressed before, but I'm unable to find an exact description of it.

I have $m$ machines, and $n$ tasks that need processing. Each task takes a variable amount of processing time, $t_i$, but this processing time is constant regardless of which machine processes it.

Each task is also assigned a variable $t_{total,i}$, which is the time at which the task is finished within the process, assuming we start at time 0.

The goal is to minimise $f=\sum_{i=0}^n t_{total,i}$, the sum of each time that each task took to be processed, including waiting time.

This naturally gives a priority to assigning the shortest tasks to be processed first, as well as to distribute the tasks fairly equally between the machines.

Is this described as a formal problem anywhere, or is a simple-case variant of a known problem?

From my research I believe it is a simplified variant of the job-shop scheduling problem, or similar to the multiple knapsack algorithm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.