(This is my very first question, if I'm doing something wrong, please tell me :))
I have n lists whose elements have an integer attribute (unique per list) and a duration in seconds.
I have to sort these lists with no coioncidence of elements with the same attribute in time, and opitimize the total duration (the duration of the longest list in time).
If there is no alternative, a gap of time is inserted until the duration of an other list element is over.
I developed an algorithm which selects an element from the longest in time adding all of the same attribute in every list
Example (edited): Every element is represented as (int att, duration time)
List 1: (1,20) (2,13) (3,15)
List 2: (1,14) (2,20) (3,14)
Optimum sorting:
List 1: (1,20) (3,15) (Gap,1) (2,13) List 1 duration: 20+15+1+13 = 49
List 2: (3,16) (2,20) (1,14) List 2 duration: 16+20+14 = 50
Total time: MAX(49,50) = 50
My algorithm:
Sorting by duration to select candidates: 1 (20+14 = 34 seconds), 2 (13+20 = 33 seconds), 3 (15+14 = 29 secs)
Final sorting:
List 1: (1,20) (2,13) (3,15) List 1 duration: 20+13+15 = 48
List 2: (2,20) (1,14) (Gap,14) (3,16) List 2 duration: 20+14+14+16 = 64
Total time: MAX(48,64) = 64
Anyone knows an algorithm which optimize the sorting?
If it is not well expressed please let me know
Sorry for my English :_)
(Edited)
I found a Thesis in Spanish presenting the problem and suggesting some solutions. It's a Job Shop Scheduling problem, as AShelly pointed out in a comment.