Given a set of n jobs with [arriving time, service duration time, penalty per unit of time] find a schedule with lowest total penalty.
- 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.