日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后,達者為師

網站首頁 編程語言 正文

C++貪心算法處理多機調度問題詳解_C 語言

作者:成就一億技術人 ? 更新時間: 2022-08-22 編程語言

多機調度問題思路

1、把作業按加工所用的時間從大到小排序

2、如果作業數目比機器的數目少或相等,則直接把作業分配下去

3、 如果作業數目比機器的數目多,則每臺機器上先分配一個作業,如下的作業分配時,是選那個表頭上 s 最小的鏈表加入新作業

可以考慮以下的貪心策略:

(1)最長處理時間作業優先的貪心選擇策略。

(2)最短處理時間作業優先的貪心選擇策略。

(3)作業到達時間優先的貪心選擇策略。

*貪?策略:優先處理花費時間長的任務,這樣可以減少短任務的等待時間.

問題描述

形式:有n個任務,m臺機器,n>m,每個作業i可以選擇?臺設備進?加?,加?時間為ti,每臺機器同時只能加??個作業,且不可中斷。實現作業調度,使得n個作業的等待時間最短。

假定有7個獨立作業,所需處理時間分別為{2,14,4,16,6,5,3},由三臺機器M1,M2,M3加工。按照貪心算法產生的作業調度如下圖所示,所需總加工時間為17.

代碼實現【C++】

#include<iostream> 
using namespace std;
#define N 7 
#define M 3 
int s[M] = { 0, 0, 0 };
//求出目前處理作業的時間和 最小的機器號 
int min(int m){
int min = 0;
int i;
for (i = 1; i<m; i++){
if (s[min]>s[i]){
min = i;
}
}
return min;
}
//求最終結果(最長處理時間) 
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;
}
//機器數大于待分配作業數 
int setwork1(int t[], int n){
int i = 0;
for (; i<n; i++){
s[i] = t[i];
}
int ma = max(s, N);
return ma;
}
//機器數小于待分配作業數 
int setwork2(int t[], int n){
int i;
int mi = 0;
for (i = 0; i<n; i++){
mi = min(M);
cout << "接下來由" << mi+1 << "號機器處理任務" << 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 << "最多耗費時間" << maxtime << endl;
}

結果

原文鏈接:https://blog.csdn.net/weixin_55764157/article/details/124519097

欄目分類
最近更新