Advertisement
Guest User

Untitled

a guest
May 30th, 2016
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.09 KB | None | 0 0
  1. Assignment:
  2. 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)
  3. Example: 4 machines, 5 operations with duration T= 3s, 5s, 6s, 8s, 9s, T min = 9s (Assigning the first two operations to one machine)
  4.  
  5. My idea:
  6.  
  7. Heaps with BOTTOMUP approach
  8.  
  9. MaxHeap (n - number of operations, n nodes)
  10. Each node will have:
  11. -Duration for each operation
  12. -Index for each operation
  13.  
  14. MinHeap(m - number of machines, m nodes)
  15. Each node will have:
  16. -TotalDuration for the operations that the machine executes
  17. -A list with the indexes for the operations that the machine executes
  18.  
  19. 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
  20. total time and the index will get added to the IndexList). Root of maxheap will get deleted
  21. 2. Resorting of the two heaps after step 1
  22. 3. Repeating step 1 until the MaxHeap is empty
  23.  
  24. 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