Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Assignment:
- You have m machines and n operations, each operations with a duration. Assign operations to the machines so that the endtime will be minimum(or close to minimum)
- Example: 4 machines, 5 operations with duration T= 3s, 5s, 6s, 8s, 9s, T min = 9s (Assigning the first two operations to one machine)
- My idea:
- Heaps with BOTTOMUP approach
- MaxHeap (n - number of operations, n nodes)
- Each node will have:
- -Duration for each operation
- -Index for each operation
- MinHeap(m - number of machines, m nodes)
- Each node will have:
- -TotalDuration for the operations that the machine executes
- -A list with the indexes for the operations that the machine executes
- 1. The element from the root of the MaxHeap will be attributed to the root of the MinHeap(execution time will get added to the
- total time and the index will get added to the IndexList). Root of maxheap will get deleted
- 2. Resorting of the two heaps after step 1
- 3. Repeating step 1 until the MaxHeap is empty
- We'll then have the MinHeap sorted and each node will contain the operations that each machine will have to execute
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement