C++貪心算法處理多機(jī)調(diào)度問題詳解
多機(jī)調(diào)度問題思路
1、把作業(yè)按加工所用的時間從大到小排序
2、如果作業(yè)數(shù)目比機(jī)器的數(shù)目少或相等,則直接把作業(yè)分配下去
3、 如果作業(yè)數(shù)目比機(jī)器的數(shù)目多,則每臺機(jī)器上先分配一個作業(yè),如下的作業(yè)分配時,是選那個表頭上 s 最小的鏈表加入新作業(yè)
可以考慮以下的貪心策略:
(1)最長處理時間作業(yè)優(yōu)先的貪心選擇策略。
(2)最短處理時間作業(yè)優(yōu)先的貪心選擇策略。
(3)作業(yè)到達(dá)時間優(yōu)先的貪心選擇策略。
*貪?策略:優(yōu)先處理花費(fèi)時間長的任務(wù),這樣可以減少短任務(wù)的等待時間.
問題描述
形式:有n個任務(wù),m臺機(jī)器,n>m,每個作業(yè)i可以選擇?臺設(shè)備進(jìn)?加?,加?時間為ti,每臺機(jī)器同時只能加??個作業(yè),且不可中斷。實(shí)現(xiàn)作業(yè)調(diào)度,使得n個作業(yè)的等待時間最短。
假定有7個獨(dú)立作業(yè),所需處理時間分別為{2,14,4,16,6,5,3},由三臺機(jī)器M1,M2,M3加工。按照貪心算法產(chǎn)生的作業(yè)調(diào)度如下圖所示,所需總加工時間為17.
代碼實(shí)現(xiàn)【C++】
#include<iostream> using namespace std; #define N 7 #define M 3 int s[M] = { 0, 0, 0 }; //求出目前處理作業(yè)的時間和 最小的機(jī)器號 int min(int m){ int min = 0; int i; for (i = 1; i<m; i++){ if (s[min]>s[i]){ min = i; } } return min; } //求最終結(jié)果(最長處理時間) int max(int s[], int num){ int max = s[0]; for (int i = 1; i<num; i++){ if (max<s[i]) max = s[i]; } return max; } //機(jī)器數(shù)大于待分配作業(yè)數(shù) int setwork1(int t[], int n){ int i = 0; for (; i<n; i++){ s[i] = t[i]; } int ma = max(s, N); return ma; } //機(jī)器數(shù)小于待分配作業(yè)數(shù) int setwork2(int t[], int n){ int i; int mi = 0; for (i = 0; i<n; i++){ mi = min(M); cout << "接下來由" << mi+1 << "號機(jī)器處理任務(wù)" << i + 1 << endl; s[mi] = s[mi] + t[i]; } int ma = max(s, M); return ma; } void main() //DEV中是int,vc++6.0中是void { int time[N] = { 16, 14, 6, 5, 4, 3, 2 };//處理時間按從大到小排序 int maxtime; if (M >= N) maxtime = setwork1(time, N); else maxtime = setwork2(time, N); cout << "最多耗費(fèi)時間" << maxtime << endl; }
結(jié)果
到此這篇關(guān)于C++貪心算法處理多機(jī)調(diào)度問題詳解的文章就介紹到這了,更多相關(guān)C++多機(jī)調(diào)度內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
斐波那契數(shù)列 優(yōu)化矩陣求法實(shí)例
斐波那契數(shù)列 優(yōu)化矩陣求法實(shí)例,需要的朋友可以參考一下2013-03-03C++數(shù)據(jù)結(jié)構(gòu)之單鏈表的實(shí)現(xiàn)
線性表的鏈?zhǔn)酱鎯τ址Q為單鏈表,它是指通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素。本文將用C++實(shí)現(xiàn)單鏈表,需要的可以參考一下2022-05-05詳解C語言結(jié)構(gòu)體中的char數(shù)組如何賦值
這篇文章主要給大家介紹了關(guān)于C語言結(jié)構(gòu)體中的char數(shù)組如何賦值的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2022-03-03C++虛函數(shù)表與類的內(nèi)存分布深入分析理解
對C++ 了解的人都應(yīng)該知道虛函數(shù)(Virtual Function)是通過一張?zhí)摵瘮?shù)表(Virtual Table)來實(shí)現(xiàn)的。簡稱為V-Table。本文就將詳細(xì)講講虛函數(shù)表的原理與使用,需要的可以參考一下2022-08-08詳解C++調(diào)用Python腳本中的函數(shù)的實(shí)例代碼
這篇文章主要介紹了C++調(diào)用Python腳本中的函數(shù) ,需要的朋友可以參考下2018-11-11C++實(shí)現(xiàn)數(shù)獨(dú)快速求解
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)數(shù)獨(dú)快速求解的方法,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-03-03