# Find a schedule with lowest total penalty

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.

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.