獨(dú)立任務(wù)最優(yōu)調(diào)度問題

1、獨(dú)立任務(wù)最優(yōu)調(diào)度問題問題描述用2臺(tái)處理機(jī)A和B處理n個(gè)作業(yè)。設(shè)第i個(gè)作業(yè)交給機(jī)器 A處理時(shí)需要時(shí)間 ai ，若由機(jī)器 B 來處理，則需要時(shí)間 bi 。由于各作業(yè)的特點(diǎn)和機(jī)器的性能關(guān)系，很可能對(duì) 于某些i，有ai>bi ,而對(duì)于某些j,j豐i，有aj>bj。既不能將一個(gè)作業(yè)分開由 2臺(tái)機(jī)器處 理，也沒有一臺(tái)機(jī)器能同時(shí)處理 2 個(gè)作業(yè)。設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，使得這 2 臺(tái)機(jī)器處理 完這 n 個(gè)作業(yè)的時(shí)間最短 ( 從任何一臺(tái)機(jī)器開工到最后一臺(tái)機(jī)器停工的總時(shí)間 )。 研究一個(gè)實(shí)例 ：(a1,a2,a3,a4,a5,a6)= (2,5,7,10,5,2);(b1,b2,b3,b4,b5,b6

2、)= (3,8,4,11,3,4)。對(duì)于給定的2臺(tái)處理機(jī)A和B處理n個(gè)作業(yè)，找出一個(gè)最優(yōu)調(diào)度方案， 使 2 臺(tái)機(jī)器處理完這 n 個(gè)作業(yè)的時(shí)間最短。輸入輸入的第1行是1個(gè)正整數(shù)n,表示要處理n個(gè)作業(yè)。接下來的2行中，每行有n個(gè) 正整數(shù)，分別表示處理機(jī) A 和 B 處理第 i 個(gè)作業(yè)需要的處理時(shí)間。輸出輸出最短處理時(shí)間。樣例輸入62 5 7 10 5 23 8 4 11 3 4樣例輸出15問題分析：此題目可以使用動(dòng)態(tài)規(guī)劃來做。難點(diǎn)是如何構(gòu)造動(dòng)態(tài)規(guī)劃算法。找出最優(yōu)子結(jié)構(gòu)和 遞推公式。有兩種構(gòu)造方法：1tijk, 表示機(jī)器 A 花費(fèi)小于等于 i 的時(shí)間，機(jī)器 B 花費(fèi)小于等于 j 的時(shí)間能 夠完成前

3、K 個(gè)任務(wù)，取值為 bool 類型 遞推公式如下：tijk=ti-akjk-1|tij-bkk-1這種構(gòu)造方法需要一個(gè)三維數(shù)組，空間和時(shí)間復(fù)雜度都相對(duì)較高2.tij,表示完成前i個(gè)任務(wù)，機(jī)器A花費(fèi)小于等于j的時(shí)間的前提下，機(jī)器 需要的最小時(shí)間。遞推公式如下：tij=mi nti-1j-ai,ti-1j+bi這種方法時(shí)間和空間復(fù)雜度相較于第一種方法較低。代碼如下：#in clude<stdio.h>#in clude<stdlib.h>#in elude <memory.h>int task_schedule(i nt *a,i nt *b,i nt n)in

4、t i,j,sum=0,min=100000;for(i=0;i< n;+i)sum += ai;int *t=(int *)malloc(sizeof(int*)*(n+1);/把 t 構(gòu)造成 int tn +1sum+1for(i=0;i<=n ;+i)ti = (int *)malloc(sizeof(i nt)*(sum+1);memset(ti,0,sizeof(i nt)*(sum+1); /數(shù)組賦初值for(i=1;i<=n ;+i)for(j=0;j<=sum;+j)if(j<ai-1)tij = ti-1j+bi-1;else if(ti-1j-ai-1>=(ti-1j+bi-1)tij = ti-1j+bi-1;elsetij = ti-1j-ai-1;for(i=0;i<=sum;+i)j = tni>i ? tni: i;if(mi n>j)min = j;return mi n;int mai n()int n,i;scan f("%d", &n);int *a=new in t n;int *b=new in t n;for(i=0;i< n;+i)sca nf("%d",&ai);for(i=0;i< n;+i)sca nf(&