Loading...
Please wait, while we are loading the content...
Similar Documents
Scheduling jobs on two uniform parallel machines to minimize the makespan
| Content Provider | Semantic Scholar |
|---|---|
| Author | Kodimala, Sandhya |
| Copyright Year | 2013 |
| Abstract | The problem of scheduling n independent jobs on m uniform parallel machines such that the total completion time is minimized is a NP-Hard problem. We propose several heuristic-based online algorithms for machines with different speeds called Q2||Cmax. To show the efficiency of the proposed online algorithms, we compute the optimal solution for Q2||Cmax using a pseudo-polynomial algorithms based on dynamic programming method. The pseudo-polynomial algorithm has time complexity O(n T )and can be run on reasonable time for small number of jobs and small processing times. This optimal offline algorithm is used to benchmark the efficiency of the proposed online algorithms. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://digitalscholarship.unlv.edu/cgi/viewcontent.cgi?article=2851&context=thesesdissertations |
| Alternate Webpage(s) | http://digitalscholarship.unlv.edu/cgi/viewcontent.cgi?article=2851&context=thesesdissertations |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |