1
$\begingroup$

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.

$\endgroup$

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.