1
$\begingroup$

Given a set of n jobs with [arriving time, service duration time, penalty per unit of time] find a schedule with lowest total penalty.

Notes:

  • Arriving time is the time when objects aarivies to processing system.
  • All objects can arrive at the same time
  • Processor is able to process only one object at the same time
  • Servicing time is the time required to process the object
  • Penalty is calculated as (penalty * time spent in the system), i.e. departure time - arrival time

The easiest way to understand the problem is to imagin a loggistic company with a number of trucks that are waitings loading/unloading of the cargo. Trucks arraives at a given time and can wait on a parking. There is only one terminal that process loading and unloading. It's required to find an optimal schedule of processing.

Example of the input data:

t,tau,a
5,4,12
4,6,2
9,2,1
11,4,5
13,4,5
16,3,2

The question here - which approach is required to solve this and similiar problems? I assume these algorithms are providing solutions close to a brute force.

$\endgroup$
2
$\begingroup$

This problem is called "minimization of total weighted flow time". It is very hard, especially when jobs cannot be preempted by the processor. Even when jobs can be preempted, it is NP-hard, so you cannot expect to have algorithms that construct optimal solutions efficiently.

If you are willing to accept non-optimal solutions, then there are efficient heuristics that find a solution of cost equal to $C$ times the optimal cost, for some large constant $C$, but they are not very practical (see the first link). A more practical approach might be to resort to a local search heuristic.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.