贪心算法：任务调度问题

数据结构课程设计报告

贪心算法：任务调度问题

专业 计算机科学与技术（软件工程） 学生姓名 陈亮 班级 BM 计算机091 学号 0951401134 指导教师 吴 素 芹 起止日期 2011.1.10-2011.1.14

目录

1简介 (1)

2算法说明 (2)

3测试结果 (2)

4分析与探讨 (8)

5小结 (11)

参考文献 (11)

附录 (12)

附录1 源程序清单 (12)

贪心算法

1 简介

贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。希望通过每次所做的贪心选择导致最终结果是问题的一个最优解。这种启发式的策略并不总奏效，然而许多情况下确能达到预期的目的。

下面来看一个找硬币的例子。假设有四种面值的硬币：一分、两分、五分和一角。现在要找给某顾客四角八分钱。这时，一般都会拿出四个一角、一个五分、一个两分和一个一分的硬币递给顾客。这种找硬币的方法与其他的方法相比，它所给出的硬币个数是最少的。在这里，就是下意思的使用了贪心算法（即尽可能地先考虑大币值的硬币）。贪心算法并不是从整体最优加以考虑，它所做出的选择只是局部最优选择。一些问题中，使用贪心算法得到的最后结果并不是整体的最优解，这时算法得到的是一次最优解（Suboptimal Solution）。在上述的问题中，使用贪心算法得到的结果恰好就是问题整体的最优解。

对于一个具体的问题，怎么知道是否可用贪心算法来解此问题，以及能否得到问题的一个最优解呢？这个问题很难给予肯定的回答。但是，许多可以用贪心算法求解的问题中一般具有两个重要的性质：贪心选择性质和最优子结构性质。

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择即贪心选择来达到，这是贪心算法可行的第一个基本要素。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终将会得到问题的一个整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且做了贪心选择后，原问题化简为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优结构性质。

得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。

贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。

可惜的是，它需要证明后才能真正运用到题目的算当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质，这个性质是该问题可用贪心算法求解的一个关键特征法中。

一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

2算法说明

有n项任务，要求按顺序执行，并设定第i项任务需要t[i]单位时间。如果任务完成的顺序为1，2，。。。，n，那么第i项任务完成的时间为c[i]=t[1]+….+t[i],平均完成时间即为（c[1]+....+c[n]）/n.本题要求找到最小的任务平均完成时间。

输入要求：

输入数据中包含几个测试案例。每一个案例的第一行给出一个不大于2000000的整数n，接着下面一行开始列出n个肺负整数t(t<=1000000000),每个数之间用空格相互隔开，以一个负数来结束输入。

输出要求：

对每一个测试案例，打印它的最小平均完成时间，并精确到0.01。每个案例对应的输出结果都占一行。若输入某一个案例中任务数目n=0,则对应输出一个空行。

输入例子：

4

4 2 8 1

-1

表示有四个任务，各自完成需要的时间单位分别是4，2，8，1，第三行输入-1表示输入结束。

输出例子：

要求程序运行后的输出结果为：6. 50

1.贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2.最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

3.贪心算法与动态规划算法的差异

贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算

法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。

贪心算法思想：

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

贪心算法的基本要素：

1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

贪心算法的基本思路：

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。

该算法存在问题：

1. 不能保证求得的最后解是最佳的；

2. 不能用来求最大或最小解问题；

3. 只能求满足某些约束条件的可行解的范围。

实现该算法的过程：

从问题的某一初始解出发；

while 能朝给定总目标前进一步 do

求出可行解的一个解元素；

由所有解元素组合成问题的一个可行解；

贪心算法的理论基础：

借助于拟阵工具，可建立关于贪心算法的较一般的理论。这个理论对确定何时使用贪心算法可以得到问题的整体最优解十分有用。

1. 拟阵

拟阵M定义为满足下面3个条件的有序对(S,I)：

(1)S是非空有限集。

(2)I是S的一类具有遗传性质的独立子集族，即若B?I，则B是S的独立子集，且B的任意子集也都是S的独立子集。空集?必为I的成员。

(3)I满足交换性质，即若A?I,B?I且|A|<|B|，则存在某一元素x?B-A，使得A∪{x}?I。

例如，设S是一给定矩阵中行向量的集合，I是S的线性独立子集族，则由线性空间理论容易证明(S,I)是一拟阵。拟阵的另一个例子是无向图G=(V,E)的图拟阵。

给定拟阵M=(S,I)，对于I中的独立子集A? I，若S有一元素x? A，使得将x加入A后仍保持独立性，即A∪{x} ? I,则称x为A的可扩展元素。

当拟阵M中的独立子集A没有可扩展元素时，称A为极大独立子集。

下面的关于极大独立子集的性质是很有用的。

定理1：拟阵M中所有极大独立子集大小相同。

这个定理可以用反证法证明。

若对拟阵M=(S,I)中的S指定权函数W，使得对于任意x?S，有W(x)>0，则称拟阵M为带权拟阵。依此权函数，S的任一子集A的权定义

为。

2. 关于带权拟阵的贪心算法

许多可以用贪心算法求解的问题可以表示为求带权拟阵的最大权独立子集问题。

给定带权拟阵M=(S,I)，确定S的独立子集A?I使得W(A)达到最大。这种使W(A)最大的独立子集A称为拟阵M的最优子集。由于S中任一元素x的权W(x)是正的，因此，最优子集也一定是极大独立子集。

例如，在最小生成树问题可以表示为确定带权拟阵的最优子集问题。求带权拟阵的最优子集A的算法可用于解最小生成树问题。

下面给出求带权拟阵最优子集的贪心算法。该算法以具有正权函数W的带权拟阵M=(S,I)作为输入，经计算后输出M的最优子集A。

Set greedy (M,W)

{A=?;

将S中元素依权值W（大者优先）组成优先队列；

while (S!=?) {

S.removeMax(x);

if (A∪I) A=A {x}∪{x};

}

return A；

}

算法greedy的计算时间复杂性为。

引理1 (拟阵的贪心选择性质)

设M=(S,I)是具有权函数W的带权拟阵，且S中元素依权值从大到小排列。又设x?S是S中第一个使得{x}是独立子集的元素，则存在S的最优子集A使得x? A。

算法greedy在以贪心选择构造最优子集A时，首次选入集合A中的元素x是单元素独立集中具有最大权的元素。此时可能已经舍弃了S中部分元素。可以证明这些被舍弃的元素不可能用于构造最优子集。

3测试结果

图5—1为正确的数据输入与其运行结果：

图5—1

图5—2为异常的数据输入与其运行结果：

。图5—2 图5—3为异常的数据输入与其运行结果：

图5—3

4分析与探讨

这个题目属于贪心算法应用中的任务调度问题。要得到所有任务的平均完成时间，只需要将各个任务完成时间从小到大排序，任务实际完成需要的时间等于它等待的时间与自身执行需要的时间之和。这样给出的调度三按照最短作业优先进行来安排的。

明确了可以用最短作业优先的思想后，就可以正式来设计题目的实现了。首先，输入的测试案例可以有很多组，每一个案例的输入格式都是第一行输入任务的个数，然后下面一行输入每一个任务需要的时间单位，输入完成另起一行，可以再继续输入下一个案例的数据。最后用一个任意的负数来表示输入的结束。这样，由于案例的个数开始不得知，所以可以套用一个for循环，如图5.13所示。

图5.13采用的for循环

所以，对每组输入，其基本过程是：读入n个任务的运行时间，进行主要的调度运算。已经明确了采用最短作业优先的程序思想，所以主要的调度运算包括3个步骤：

（1）排序：将数组按从小到大排序。

排序方法很多，如：冒泡排序、希尔排序、堆排序）此题用希尔排序实现，如图5.14所示.

它的基本思想是：先取一个小于n的整数d

1

作为第一个增量；这里选取n的一

半作为第一个增量（increment=>>1），把数组的全部元素分成d

1

个组。所以距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个

增量d

2

1

重复上述的分组和排序，直至所取的增量d

t=

1(d

t

t-1

<…

2

1

),即所有记

录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入排序方法。

图5.14 希尔排序的实现

（2）计算总的平均完成时间：排序完成后，数组a中的元素以升序的方式排序，因此总的平均完成时间为

ACT=∑a[i] ×(n-i)/n

（3）输出调度结果：由于输出的结果要求精确到0.01，所以输出的时候需要采用以下输出格式。

图5.15 要求输出的精度为0.01

另外，程序实现的时候，要求用户一次可以输入一组或多组测试案例的数据，当用户的输入完成后，程序经过计算在屏幕上分行显示这几个案例的结果。因此,在有多个测试案例的情况下，需要设置一个数组，用来存放每一组测试案例的计算结果，如图5.16所示

图5.16 有多个测试案例的处理方法

5小结

通过这次课程设计的学习，更加深刻认识了数据结构的重要性。在课程设计过程中，经过互相的提问，仔细的思考，学会了许多数据结构里之前不懂的问题。很高兴，学会了新的东西。我做的是贪心算法的课程设计，对于这个算法它很有趣，即通过一系列的选择，来选取最好的选择。而且还有许多的应用实例，使我们对算法有了更好的理解。感觉数据结构还是蛮好玩的，就是一个算法就可以控制整个的过程。

为了把数据结构学好，不仅要弄好理论上的，而且还要把课程设计学好，联系实际，根据理论把课程设计学好，两者结合。相信一定是可以学好的。通过自己的努力就可以，结果不是那么重要，学到了东西才是最好的。相信自己。

参考文献

[1] 刘振安,刘燕君.C程序设计课程设计[M].[北京]机械工业出版社,2004年9月

[2] 谭浩强.C程序设计（第三版）.清华大学出版社,2005年7月

[3] 严蔚敏,吴伟民.数据结构（C语言版）.清华大学出版社,1997年4月

[4]Mark Allen Weiss,陈越改编.Data Structures and Algorithm Analysis in

C(second edition).北京：人民邮电出版社，2005

[5]魏宝刚，陈越，王申康.数据结构与算法分析.杭州：浙江大学出版社，2004

[6]书本教材 C语言程序设计

[7]书本教材 C++程序设计

[8]书本教材数据库理论

附录

附录1 源程序清单

#include

#include

#include

using namespace std;

void Shellsort( long *a, long n );

int main()

{

long n,i,j;

long *a,*b;

double r[100];/**** 用来存放每个测试案例的计算结果***/

j=0;/*** 记录测试案例的个数***/

/*****读入用户的输入，若当前输入为负数，则程序终止******/ for( n = 0; n >= 0 ; )

{

scanf( "%ld", &n );

if(n > 2000000){

printf("too much for the project!\n");

exit(0);

}

if( n > 0 )

{

b = (long*)malloc( n * sizeof( long ) );

a = b;

for(i=0; i< n ; i++)

{

scanf( "%ld", b+i );

/*** 检查输入的数据是否大于1000 000 000****/

if(*(b+i) > 1000000000){

printf("too much for the project!\n");

exit(0);

}

/*** 对输入中出现任务时间为负数的异常处理******/

if(*(b+i)<0)

{

printf("input error！\n");

return 0;

}

}

Shellsort( b, n );

/***** 计算平均完成时间*****/

for( i = n, r[j] = 0.0; i > 0 ; i--,a++ )

{

r[j]+= (double)*a/(double)n * i;

}

j++;

free( b );

}

/*** 当n为0时，标志相应的r数组值为－1，输出时碰到－1则输出一个空行***/

else if ( n == 0 )

{

r[j++]=-1;

}

}

for(i=0;i

{

if(r[i]==-1)printf("\n");/** 输出一个空行**/

else

printf( "%.2f\n", r[i] );/** 输出的结果要求精确到0.01 **/

}

return 1;

}

/*** 希尔排序方法***/

void Shellsort( long *a, long n )

{

long i, j, increment;

long temp;

/** 第一个增量值为(n/2)，以后每一次的增量都是上一个增量值的一半**/ for( increment = n>>1; increment>0; increment>>=1 )

{

for(i = increment; i < n; i++)

{

temp = *(a+i);

for(j = i; j>=increment; j-= increment)

{

if( temp < *(a + (j-increment)) )

*(a+j)= *( a+ (j-increment) );

else

break;

}

*(a+j) = temp;

}

}

}

课程设计报告-贪心算法：任务调度问题

数据结构课程设计报告 贪心算法：任务调度问题的设计 专业 学生姓名 班级 学 号 指导教师 完成日期

贪心算法：任务调度问题的设计 目录 1设计内容 (1) 2）输入要求 (1) 3）输出要求 (1) 2设计分析 (1) 2.1排序（将数组按照从小到大排序）的设计 (1) 2.2多个测试案例的处理方法的设计 (2) 2.3 for循环设计 (2) 2.4系统流程图 (2) 3设计实践 (2) 3.1希尔排序模块设计 (2) 3.2 多个测试案例的处理方法的模块设计 (3) 4测试方法 (4) 5程序运行效果 (4) 6设计心得 (6) 7附录 (6)

数据结构课程设计报告（2017） 贪心算法：任务调度问题的设计 1设计内容 有n项任务，要求按顺序执行，并设定第I项任务需要t[i]单位时间。如果任务完成的顺序为1，2，…，n，那么第I项任务完成的时间为c[i]=t[1]+…+t[i]，平均完成时间（ACT）即为（c[1]+..+c[n]）/n。本题要求找到最小的任务平均完成时间。 2）输入要求 输入数据中包含n个测试案例。每一个案例的第一行给出一个不大于2000000的整数n，接着下面一行开始列出n各非负整数t（t≤1000000000），每个数之间用空格相互隔开，以一个负数来结束输入。 3）输出要求 对每一个测试案例，打印它的最小平均完成时间，并精确到0.01。每个案例对应的输出结果都占一行。若输入某一个案例中任务数目n=0，则对应输出一个空行。 2 设计分析 这个题目属于贪心算法应用中的任务调度问题。要得到所有任务的平均完成时间，只需要将各个任务完成时间从小到大排序，任务实际完成需要的时间等于它等待的时间与自身执行需要的时间之和。这样给出的调度是按照最短作业优先进行来安排的。贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。在许多可以用贪心算法求解的问题中一般具有两个重要的性质：贪心选择性质和最有子结构性质。所谓贪心选择性只是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，这是贪心算法可行的第一基本要素。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终将会得到问题的一个整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且做了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。当一个问题的最优解包含着它的子问题最优解时，称此问题具有最优子结构性质，这个性质是该问题可用贪心算法求解的一个关键特征。 2.1排序（将数组按照从小到大排序）的设计 排序的方法有很多，如：冒泡排序、希尔排序、堆排序等，这些排序的方法都可以使用。这里采用希尔排序来实现。 它的基本思想是：先取一个小于n的整数d1作为第一个增量；这里选取n的一半作为第一个增量（increment=n》1），把数组的全部元素分成d1个组。所有距

算法之多机调度问题

算法之多机调度问题 用贪心法解决多机调度问题 （1）问题的描述 设有n个独立的作业{1, 2,…, n}，由m台相同的机器{M1, M2,…, Mm}进行加工处理，作业i所需的处理时间为ti（1≤i≤n），每个作业均可在任何一台机器上加工处理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 （2）算法设计思想 解多机调度问题的贪心策略是最长处理时间作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。 （3）数据及解题过程 设7个独立作业{1, 2, 3, 4, 5, 6, 7}由3台机器{M1, M2, M3}加工处理，各作业所需的处理时间分别为{2, 14, 4, 16, 6, 5, 3}。贪心法产生的作业调度如下： （4）程序使用C++运行测试 （5）代码如下： #include #include using namespace std; //冒泡法对作业时间t降序排列，作业编号p的顺序也随t的顺序改变而改变，这点很重要！ void Dsc_Order_By_t(int t[],int p[],int n) //注意：数组元素下标从1开始{ //你的代码 int i,j;

for (i=1;i<=n;i++) { for (j=1;j<=n-i;j++) { if (t[j]

实验二(贪心算法)

华东师范大学计算机科学技术系上机实践报告 课程名称：算法设计与分析年级：05上机实践成绩： 指导教师：柳银萍姓名：张翡翡 上机实践名称：贪心算法学号：10052130119上机实践日期：2007-4-10 上机实践编号：NO.2组号：上机实践时间：10:00-11:30 一、目的 了解熟悉掌握贪心算法实质并学会灵活运用，从而解决生活中一些实际问题。 二、内容与设计思想 1.超市的自动柜员机(POS)要找给顾客各种数值的现金，表面上看，这是一个很简单的任务，但交给机器办就不简单了。你作为一个计算机专家，要求写一个程序来对付这个“简单”的问题。 你的自动柜员机有以下的币种：100元，50元，20元，10元，5元，2元，1元。你可以假设每种钱币的数量是无限的。现在有一笔交易，需要找个客户m元，请你设计一个算法，使得找给顾客的钱币张数最少。 要求： 输入：第一行仅有一个整数n(0

(完整版)智能算法在柔性车间调度中的应用

智能算法在柔性作业车间调度中的应用摘要：为提高企业生产效率，合理的流水车间生产调度显得尤为重要。本文介绍了三种智能算法（蚁群算法、遗传算法、改进粒子群算法）在车间生产调度中的应用，主要介绍了算法的基本思想、模型结构、算法实现以及运用前景。对智能算法在生产调度中的应用做出总结。 关键字：智能算法；蚁群算法；遗传算法；改进粒子群算法；生产调度 0.前言 柔性作业车间调度问题(Flexible job-shop sche- duling problem, FJSP)是传统作业车间调度 问题的扩展，是实际生产中迫切需要解决的一类问 题。在传统的作业车间调度问题中，工件的每道工序只能在一台确定的机床上加工。而在柔性作业车间调度问题中，每道工序可以在多台机床上加工，并且在不同的机床上加工所需时间不同。柔性作业车间调度问题减少了机器约束，扩大了可行解的搜索范围，增加了问题的难度。 作业车间的主要特点是：n个工件需要在m台机器上进行加工，每个工件都有其独特的加工步骤，但无明显的顺序约束，并且加工时间是已知的，调度的目标是在不允许两个工件同时在同一台机器上加工的前提下，如何安排工件在每台机器上的加工顺序使这些工件能够尽快加工完毕[1]。 1.蚁群算法在作业车间的应用[2] 以3个工件2台机器的问题作为例子，如图1。 图1 三个工件两台机器的JSP问题 为确定先对哪个工件进行加工，需要设置一个初始节点O0，所有的蚂蚁最初都放置在O0。图1中除与O0相连的有向弧表示同一个工件的加工顺序，工件必须按照该顺序进行加工。其它则为无向弧。每个弧与表示节点间信息素的量和启发式距离的一对 值{αij, d ij}有关。d ij 通常为对节点 j 的第 i 步操作的加工时间，τij使用蚁周方式进行更新：其中，ρ是个系数，1?ρ表示在时间t和t+1之间信息素的蒸发，Q为常数，Tk为完成所有加工步骤后最短的总加工时间。初始时刻τij(0)= c（c为常数）。 这个规则包含了两个方面：(1)图1中所有边缘上的信息素都要蒸发；(2)完成所有的加工后要将该解的效果加到各边缘上。蒸发可以防止搜索局限在局部最小的邻域中，另一方面又能根据已有解的效果好坏来更新信息素，进行增强学习。 另一个关键的问题就是如何保证蚂蚁按照工件的工艺路线产生一组可行解。这里用到3个集合：对每个蚂蚁 k，首先要有集合G k，表示没有访问过的节点集合；S k 表示根据技术路线下一步允许访问的节点集合；还需要一个禁忌表，存放已经访问过的节点。在我们的例子中， G k ={1，2 ，3，4，5 ，6}，S k ={1，2 ，3}。转移概率是通过下式计算的： T ij 为工件i在机器j上的加工时间。每选择一个节点，该节点就被追加到禁忌表中并从G k和 S k中删除；如果被选的节点不是工件的最后一步，那该工件中紧邻的下一个节点会被加到Sk中。该过程一直重复到G k = φ。最后禁忌表中得到的节点的排列顺序就是蚂蚁 k 找到的解。 参数α和β决定了算法的收敛速度并对解的性能好坏有重要影响，同时蒸发常数也需要进行适当的调整以使搜索能在好的搜索空间中进行，并防止陷入局部最优的邻域中。

作业车间调度模型

基于WSA算法的作业车间低碳调度方法研究 1.1 引言 本章主要研究了以最大化完工时间和能耗指标为目标的作业车间低碳调度模型的求解方法。首先，建立了多目标作业车间低碳调度模型；然后基于Pareto 支配理论，设计了一种高效的MODWSA算法获得满意的Pareto非支配解；最后，设计了一套测试算例，将MODWSA算法与其它经典多目标算法进行比较分析，验证了MODWSA算法的优越性。在本研究中，作者完成了两项工作：首先，构建了一个新的多目标作业车间低碳数学模型；其次，设计了一种高效的MODWSA算法获得满意的Pareto非支配解。 1.2 作业车间低碳调度模型 本章研究的作业车间低碳调度问题可描述如下：对给定的n个工件及k台机器，一个工件的加工需要经过m道工序，每道工序允许在特定的机器上加工，任意一台机器在任意一个时刻仅能加工某一工件的某一道工序，并且一个工件只能在其上道工序完成后下一道工序才能开始加工[插入文献]。 考虑机器的准备时间，准备时间与同一机器上相邻两工件的加工顺序相关，并且机器的启动和工件的加工是相连的。对应于不同工序，机器具有不同的速率档位进行加工，并且可以进行调节。从能耗的角度来看，机器有四种不同的状态：加工状态(机器在加工工件)，启动状态（机器在准备加工一个新的工件），待机状态（机器处于空转中），以及关机状态（机器被关机）。通常情况下，当机器在较高速率运作时，工件的加工时间会被缩短，但是相应的能耗会增加。因此本问题以最大化完工时间和能耗指标为目标，由于本章所研究问题的特点，该问题要比传统的作业车间调度问题要复杂的多。在该问题中，其它设定如下： ●工件在车间里被连续加工。也就是说，加工过程不能被中断。 ●机器允许有空闲时间，并且各阶段间具有容量无限的缓冲区。 ●当有第一个工件在机器上加工时，机器开机；当在该机器上加工的所有工件 加工完毕后，机器关机。 ●机器速度在工件加工过程中不能进行调整。 1.2.1 混合整数规划模型 为了提出问题的数学模型，根据上面对问题的描述，我们首先定义了下面的相关数学符号。

多处理机调度问题的一种近似算法

1997年7月 烟台大学学报(自然科学与工程版) July1997第10卷第3期 Journal of Yantai U niversity(N atural Science and Eng ineering) Vol.10No.3 多处理机调度问题的一种近似算法 程建纲 (烟台大学数学与信息科学系,烟台264005) 秦成林 (上海大学数学系,上海201800) 摘要 对多处理机调度问题P C max,给出一种近似算法.大量实例的计算结果 表明,本文的算法是非常有效的. 关键词 组合优化 排序 近似算法 随机算法 中图分类号 O224 多处理机调度问题P C max考虑有n个独立的工件和m台相同的机器,每一工件在并且仅在一台机器上加工一次,同时在加工时不允许中断加工的情形,所讨论的问题为:确定工件在各机器上的分配方案,使得从第一个被加工工件开始加工时刻起到全部工件加工完毕时刻止的时间跨度取极小.由于它在许多领域中都有广泛的应用,同时又是一个NP-C 问题,故其近似算法的研究受到广泛重视[1,2].本文对此问题通过随机迭代来给出一种近似算法,并通过大量的计算实例来表明对通常的P C max问题,本文的算法能够获得精度很高的近似解,而且在许多情况下也能获得问题的精确解. 下面首先给出本文中对此问题的数学描述形式.设m,n是正整数,R n+表示分量全为正数的n维向量的全体,同时为了方便起见,在本文中,对任意的向量,其分量始终用括号的形式表示,例如对l R n+,其相应的n个分量为l(1),l(2),!,l(n),另外对j所满足的条件组 ,以?{l(j)|条件组 }表示对所有j满足条件组 的分量l(j)做累加,以M表示由 {1,2,!,n}到{1,2,!,m}的映象全体所构成的空间,此时l R n+表示n个工件的工件组,其中第j个工件的加工时间为l(j),q M表示对工组的一个分配方案,它将第j个工件分配给第q(j)号机器,进而P C max问题为:对给定的l R n+,极小化问题 min max 1#i#m?{l(j)|q(j)=i} s.t q M(P)为了便于描述本文对此问题的算法,再引进以下一些记号,以R m表示通常的m维空间, [0,h]n表示R n中所有分量都不超过h的n维非负向量的全体,以S n表示{1,2,!,n}上的全体置换所构成的n次对称群,对l R n+, S n,l 表示向量(l( (1)),l( (2)),!, l( (n))),映象A:R n+?M%R n+的定义为A(l,q)的第n个分量A(l,q)(j)=?{l(k)|q(k)=q(j),k&j},映象D:R n+%S n的定义为:对y R n+,D(y)由以下两条件唯一确定:

算法设计与分析课程大作业

题目作业调度问题及算法分析 学院名称：计算机与信息工程学院 专业名称：计算机科学与技术

目录 《算法设计与分析》课程大作业.................................................................... 错误!未定义书签。一．动态规划算法解决流水作业调度. (4) 1、问题描述 (4) 2、算法分析 (4) 3. 算法的描述 (5) 4、部分算法实现 (6) 5. 运行结果 (8) 6、时空效率分析 (8) 二．贪心算法解多机调度问题 (8) 1、问题描述 (8) 2、算法分析 (9) 3.部分算法实现 (9) 4.计算复杂性分析 (11) 5. 运行结果 (12) 三．回溯法解决批作业调度问题 (12) 1.问题描述 (12) 2.算法思想 (13) 3. 部分算法实现 (14) 4.运行结果 (15) 5.时间复杂性分析 (15) 四．作业调度算法比较 (16) 五．课程学习总结 (16)

摘要： 在现代企业中，作业调度已成为提高资源利用率、从而提高企业运行效益的关键环节之一。把各个作业分配到车间现有的设备上，并确定它们的先后次序，这是一项复杂的工作本文就作业调度排序问题进行了研究，通过对几个经典作业调度算法的分析讨论，总结了各个算法对作业调度的求解过程，并给出了每个算法的复杂度及性能分析。 关键词：作业调度；动态规划；贪心算法；回溯法；

一．动态规划算法解决流水作业调度 1、问题描述 给定n 个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i 在机器j 上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n 个作业。 2、算法分析 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。 在一般情况下，机器M1开始加工S 中作业时，机器M2还在加工其他作业，要等时间t 后才可利用。将这种情况下完成S 中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。 由流水作业调度问题的最优子结构性质可知， )}},{({min )0,(1i i n i b i N T a N T -+=≤≤（1）

02流水线车间生产调度的遗传算法MATLAB源代码

流水线车间生产调度的遗传算法MATLAB源代码 n个任务在流水线上进行m个阶段的加工，每一阶段至少有一台机器且至少有一个阶段存在多台机器，并且同一阶段上各机器的处理性能相同，在每一阶段各任务均要完成一道工序，各任务的每道工序可以在相应阶段上的任意一台机器上加工，已知任务各道工序的处理时间，要求确定所有任务的排序以及每一阶段上机器的分配情况，使得调度指标(一般求Makespan)最小。 function [Zp,Y1p,Y2p,Y3p,Xp,LC1,LC2]=JSPGA(M,N,Pm,T,P) %-------------------------------------------------------------------------- % JSPGA.m % 流水线型车间作业调度遗传算法 % GreenSim团队——专业级算法设计&代写程序 % 欢迎访问GreenSim团队主页→https://www.wendangku.net/doc/db3371575.html,/greensim %-------------------------------------------------------------------------- % 输入参数列表 % M 遗传进化迭代次数 % N 种群规模(取偶数) % Pm 变异概率 % T m×n的矩阵，存储m个工件n个工序的加工时间 % P 1×n的向量，n个工序中，每一个工序所具有的机床数目 % 输出参数列表 % Zp 最优的Makespan值 % Y1p 最优方案中，各工件各工序的开始时刻，可根据它绘出甘特图 % Y2p 最优方案中，各工件各工序的结束时刻，可根据它绘出甘特图 % Y3p 最优方案中，各工件各工序使用的机器编号 % Xp 最优决策变量的值，决策变量是一个实数编码的m×n矩阵 % LC1 收敛曲线1，各代最优个体适应值的记录 % LC2 收敛曲线2，各代群体平均适应值的记录 % 最后，程序还将绘出三副图片：两条收敛曲线图和甘特图（各工件的调度时序图） %第一步：变量初始化 [m,n]=size(T);%m是总工件数，n是总工序数 Xp=zeros(m,n);%最优决策变量 LC1=zeros(1,M);%收敛曲线1 LC2=zeros(1,N);%收敛曲线2 %第二步：随机产生初始种群 farm=cell(1,N);%采用细胞结构存储种群 for k=1:N X=zeros(m,n); for j=1:n for i=1:m X(i,j)=1+(P(j)-eps)*rand;

贪 心 算 法

【贪心算法】思想 & 基本要素 & 贪心算法与局部最优 & 贪心算法与动态规划的区别 & 运用贪心算法求解问题 首先我们先代入问题来认识一下贪心算法涉及的问题 找钱问题 给顾客找钱，希望找零的钞票尽可能少，零钱种类和数量限定 找钱问题满足最优子结构 最快找零（贪心）：为得到最小的找零次数，每次最大程度低减少零额活动安排问题 设个活动都需要使用某个教室，已知它们的起始时间和结束时间，求合理的安排使得举行的活动数量最多 贪心：使得每次安排后，教室的空闲时间最多 解决过程如下： 贪心算法求得的相容活动集是最大的 第一步：证明最优解中包含结束时间最早的活动 设相容集 A 是一个最优解，其结束最早的活动为 a，则 ( A - { a }) U { 1 } 也是一个最优解 第二步：证明去掉结束时间最早的活动后，得到的子问题仍是最优的：反证法 理解贪心算法 贪心算法总是做出当前最好的选择 贪心选择的依据是当前的状态，而不是问题的目标

贪心选择是不计后果的 贪心算法通常以自顶向下的方法简化子问题 贪心算法求解的问题具备以下性质 贪心选择性质：问题的最优解可以通过贪心选择实现 最优子结构性质：问题的最优解包含子问题的最优解 贪心选择性质的证明 证明问题的最优解可以由贪心选择开始 即第一步可贪心 证明贪心选择后得到的子问题满足最优子结构 即步步可贪心 背包问题 问题描述：给定 n 个物品和一个背包。物品 i 的重量为 Wi ，价值为 Vi ，背包的容量为 c ，问如何选择物品或物品的一部分，使得背包中物品的价值最大？ 当 n = 3 ，c = 50 0-1背包问题：装入物品2、3，最大价值220 背包问题：装入物品1、2和2-3的物品3，最大价值240（贪心算法）贪心算法无法求解0-1背包问题，按贪心算法，0-1背包问题将装入物品1和2 贪心与局部最优 思考：为什么0-1背包可以用动态规划？而不能用贪心算法 贪心易陷入局部最优

贪心算法求解多机调度问题

贪心算法求解多机调度问题 设有n项独立的作业{1,2,…, n},由m 台相同的机器加工处理。作业i 所需要的处理时间为台相同的机器加工处理。设有n 项独立的作业由ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分成更小的子作业。多机调度问题要求给出一种调度方案，能拆分成更小的子作业。多机调度问题要求给出一种调度方案，使所给的n 个作业在尽可台机器处理完。利用贪心策略，设计贪心算法解决多机调度问题，能短的时间内由m 台机器处理完。利用贪心策略，设计贪心算法解决多机调度问题，并计算其时间复杂度。 多机调度问题的一个实例： 多机调度问题的一个实例：项独立的作业{1,2,3,4,5,6,7}，要由三台机器M1, M2 ,M3 处理。各个作业所需处理。各个作业所需例如设有7 项独立的作业，要的处理时间分别为{2,14,4,16,6,5,3}。利用你设计的贪心算法，要的处理时间分别为。利用你设计的贪心算法，安排作业的处理顺序使得机器处理作业的时间最短。器处理作业的时间最短。 #include using namespace std; void Greedy(int t[],int n,int m); int main() { int n=7,m=3,t[]={2,14,4,16,6,5,3};//待分配的工作

Greedy(t,n,m); return 0; } void Greedy(int t[],int n,int m) { int flagn,flagm; int M[]={0,0,0,0,0,0,0,0}; for(int i=0;iM[j]) {flagm=j;} } M[flagm]=M[flagm]+t[flagn]; t[flagn]=0; //被选择过的机器时间调为0 cout<

贪心算法经典问题：活动安排,背包问题,最优装载,单源最短路径 Dijiksra,找零钱问题,多机调度

活动安排 public static int greedySelector(int [] s, int [] f, boolean a[]) { //s[]开始时间f[]结束时间 int n=s.length-1; a[1]=true; int j=1; int count=1; for (int i=2;i<=n;i++) { if (s[i]>=f[j]) { a[i]=true; j=i; count++; } else a[i]=false; } return count; } 背包问题 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w); //以每种物品单位重量的价值Vi/Wi从大到小排序 int i; for (i=1;i<=n;i++) x[i]=0; float c=M; for (i=1;i<=n;i++) { if (w[i]>c) break; x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; //允许放入一个物品的一部分 } 最优装载 void Loading(int x[], T ype w[], T ype c, int n) { int *t = new int [n+1]; //t[i]要存的是w[j]中重量从小到大的数组下标Sort(w, t, n); //按货箱重量排序 for (int i = 1; i <= n; i++) x[i] = 0; //O(n) for (int i = 1; i <= n && w[t[i]] <= c; i++) {x[t[i]] = 1; c -= w[t[i]];} //调整剩余空间 } 单源最短路径Dijiksra template void Dijikstra(int n, int v, Type dist[], int prev[], Type **c) { //c[i][j]表示边(i,j)的权，dist[i]表示当前从源到顶点i的最短特殊路径bool s[maxint]; for(int i= 1;i<=n; i++) { dist[i]=c[v][i]; s[i]=false;

matlab生产调度问题及其优化算法

生产调度问题及其优化算法（采用遗传算法与MATLAB编程） 信息014 孙卓明 二零零三年八月十四日

生产调度问题及其优化算法 背景及摘要 这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能导致相当大的调度规模。解空间容量巨大，N个工件、M台机器的问题包含M ( N)! 种排列。由于问题的连环嵌套性，使得用图解方法也变得不切实际。传统的运筹学方法，即便在单目标优化的静态调度问题中也难以有效应用。 本文给出三个模型。首先通过贪婪法手工求得本问题最优解，既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法，采用MATLAB 软件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列问题的有效解决具有一定参考和借鉴价值。 一．问题重述 某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工， 条件：1、每件产品必须按规定的工序加工，不得颠倒； 2、每台设备在同一时间只能担任一项任务。 （每件产品的每个工序为一个任务） 问题：做出生产安排，希望在尽可能短的时间里，完成所接受的全部任务。 要求：给出每台设备承担任务的时间表。 注：在上面，机器 A，B，C，D 即为机器 1，2，3，4，程序中以数字1，2，3，4表示，说明时则用A，B，C，D

第四章-贪心算法(模拟试题)

计算机与信息科学学院2010-2011学年第2学期模拟试卷 计算机算法设计与分析—第四章.贪心算法 本卷满分100分 完卷时间120分钟 一. 简答题（每小题2分，共20分） 1. 当一个问题具有 且具有 时可用贪心算法，如最小生成树问题（背包问题，活动安排问题等）。 2. 在动态规划可行的基础上满足 才能用贪心。 3. 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的 选择。 4. 动态规划算法通常以 的方式解各子问题，而贪心算法则通常 以 的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题 5. 贪心算法和动态规划算法都要求问题具有 性质，这是2类算法的一个共同点。 6. 当一个问题的最优解包含其子问题的最优解时，称此问题具有 。 7. 对于具有n 个顶点和e 条边的带权有向图，如果用带权邻接矩阵表示这 个图，那么Dijkstra 算法的主循环体需要 时间。这个循环需要执行n-1次，所以完成循环需要 时间。算法的其余部分所需要时间不超过 。 8. 0-1背包问题指：给定n 种物品和一个背包。物品i 的重量是Wi ，其价值为Vi ，背包的容量为C 。应如何选择装入背包的物品，使得装入背包中物品的 最大。 9. 有一批集装箱要装上一艘载重量为c 的轮船。其中集装箱i 的重量为Wi 。最优装载问题要求确定在 不受限制的情况下，将 装上轮船。 10. 多机调度问题要求给出一种作业调度方案，使所给的n 个作业在 由m 台机器加工处理完成。 二. 综合题（1-6题每题7分，7-8题每题9分，共60分） 1. 有4个物品，其重量分别为(4, 7, 5, 3)，物品的价值分别为(40, 42, 25, 12)，背包容量为10。试设计3种贪心策略,并给出在每种贪心策略下背包问题的解。 )(n O

企业战略混合遗传模拟退火算法解决多机调度问题

企业战略混合遗传模拟退火算法解决多机调度问题 Ting Bao was revised on January 6, 20021

★★★文档资源★★★ 摘要：将模拟退火引入遗传算法，构造混合遗传模拟退火算法。通过对具体多机调度问题的求解，表明混合遗传模拟退火算法的效率要优于单一的遗传算法和模拟退火算法。 关键词：多机调度；遗传算法；模拟退火算法；混合遗传模拟退火算法 作业调度问题是生产管理与控制的一个基本问题。按照加工设备数量和加工作业的流动方式，一般可分为单机调度、并行机调度、Flowshop调度、可重入式调度和Jobshop调度等多种类型。作业调度中的许多问题，不仅具有随机性、约束复杂、规模大及多目标冲突等特点，而且许多都属于NP完全问题，即使在单机情形也是如此。因此，如何寻求有效可行的调度求解方案，一直是生产管理与控制研究的热点和难点。 一、多机调度问题的数学模型 二、算法分析 自Davis首次将遗传算法（Genetic Algorithms，GA）引入到调度问题的研究中以来，进化算法（包括遗传算法）在制造生产零件和生产调度研究领域获得了广泛的应用，并取得了较好的优化效果。遗传算法用于求解某些并行多机调度问题也有不少的研究成果。遗传算法的优点是：不受搜索空间的****性假设的约束，不必要求诸如连续性、导数存在和单峰的假设，并且具有内在的并行性，收敛速度快，能够解决非常困难的寻优问题。当然，传统的遗传算法也有许多缺点，其中最为严重的是“过早收敛”问题。所谓“过早收敛”是指在搜索的初期，由于优良个体急剧增加使种群失去多样性，从而造成程序陷入局部，达不到全局最优解的现象。遗传算法的另一个缺陷是“GA欺骗”问题，即在GA的搜索过程中，有可能搜索到最优解然后又发散出去的现象。另外，遗传算法还有参数选择未能定量和不能精确定位最优解等缺陷。 模拟退火算法（Simulated Annealing，SA）又称为模拟冷却法、统计冷却法、Monte－Carlo退火法、随机松弛法和概率爬山法等。模拟退火算法是一种新的统计优化方法，其思想最早是由N．Metropolis等人借鉴统计力学中物质退火方法而提出的。1983年Kirkpatrick等人开展了一些富有成效的工作，成功地将该思想引入组合优化理论。模拟退火算法源于对固体退火过程的模拟，采用Meteropolis接受准则，并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。模拟退火算法的主要优点之一就是能以一定的概率接收目标函数值不太好的状态。即算法不但往好的方向走也可向差的方向走；这使得算法即便落入局部最优的陷阱中，理论上经过足够长的时间后也可跳出来从而收敛到全局最优解。模拟退火算法的主要缺点是解的质量与求解时间长短之间的矛盾。为得到一个好的近似最优解，需要进行反复迭代运算，当问题的规模不可避免地增大时，缺乏可行的解决途径。

作业调度快速贪心算法

作业调度快速贪心算法 班级：08级通信三班学号：14081403173 姓名：阮晨 成绩：分 一、设计目的 1.掌握贪心算法的思想； 2.掌握贪心算法的典型问题，如作业调度问题； 3.进一步多级调度的基本思想和算法设计方法； 4.提高分析与解决问题的能力。 二、设计内容 1．任务描述 1）多段图问题简介 在无资源约束且每个作业可在等量的是时间内完成的作业调度问题中，可以拟定一个最优解的算法，制定如何选择下一个作业的量度标准，使得所选择的下一个作业在这种量度下达到最优。快速贪心算法利用减少作业移动—分配最晚时间片原则使得作业在最短的时间片内达到最大的效益值。 2）设计任务简介 设计快速贪心算法实现在效益p=(35, 30, 25, 20, 15, 10, 5, 1),时间期限 d=(4, 2, 4, 5, 6, 4, 5, 7)条件下的最大效益，输出作业的调度序列。 2．快速贪心算法的实现过程 已知n=8, p=(35, 30, 25, 20, 15, 10, 5, 1), d=(4, 2, 4, 5, 6, 4, 5, 7)。设计、编程实现作业调度快速贪心算法, 要求按作业调度顺序输出作业序列。 案例分析： 可用最晚空闲时间片序号数组 F[]。 存储截止期限值为 i 的作业可用的最晚空闲时间片序号。 初始状态: F[0:k]={0, 1, 2, 3, …, k-1, k},k = min { n, max {dj} } 竞争可用最晚空闲时间片的截止期限值集合 set[0:k] 在树结构表示下, 初值为： set[0:k]={{0,-1},{1, -1},{2, -1},{3, -1}, …,{k-1, -1},{k, -1}}. 如下表：

生产调度问题及其优化算法

生产调度问题及其优化算法 <采用遗传算法与MATLAB编程） 信息014 孙卓明 二零零三年八月十四日 生产调度问题及其优化算法 背景及摘要 这是一个典型的Job- Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job- Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能导致相当大的调度规模。解空间容量巨大，N个工件、M台机器的问题包含种排列。因为问题的连环嵌套性，使得用图解方法也变得不切实际。传统的运筹学方法，即便在单目标优化的静态调度问题中也难以有效应用。 本文给出三个模型。首先通过贪婪法手工求得本问题最优解，既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法，采用MATLAB软件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列问题的有效解决具有一定参考和借鉴价值。 一．问题重述 某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工，其 工序产品 1 2 3 4 5 6 7 8 S T S T S T S T S T S T S T S T 1 C 8 A 2 B 4 C 24 D 6 2 A 4 D 5 B 3 C 4 3 C 3 D 7 A 15 B 20 A 8 4 B 7 C 6 D 21 A 1 D 16 C 3 5 D 10 B 4 C 8 D 4 A 12 C 6 D 1 6 A 1 B 4 A 7 C 3 D 5 A 2 C 5 A 8 条件：1、每件产品必须按规定的工序加工，不得颠倒； 2、每台设备在同一时间只能担任一项任务。 <每件产品的每个工序为一个任务）

贪心算法多机调度问题c程序

实验内容：多机调度问题 设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i所需要的处理时间为台相同的机器加工处理。设有n项独立的作业由ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分成更小的子作业。多机调度问题要求给出一种调度方案，能拆分成更小的子作业。多机调度问题要求给出一种调度方案，使所给的n个作业在尽可台机器处理完。利用贪心策略，设计贪心算法解决多机调度问题，能短的时间内由m台机器处理完。利用贪心策略，设计贪心算法解决多机调度问题，并计算其时间复杂度。 多机调度问题的一个实例： 多机调度问题的一个实例：项独立的作业{1,2,3,4,5,6,7}，要由三台机器M1, M2 ,M3处理。各个作业所需处理。各个作业所需例如设有7项独立的作业，要的处理时间分别为{2,14,4,16,6,5,3}。利用你设计的贪心算法，要的处理时间分别为。利用你设计的贪心算法，安排作业的处理顺序使得机器处理作业的时间最短。器处理作业的时间最短。 #include using namespace std; void Greedy(int t[],int n,int m); int main() { int n=7,m=3,t[]={2,14,4,16,6,5,3};//待分配的工作 Greedy(t,n,m); return 0; } void Greedy(int t[],int n,int m) { int flagn,flagm; int M[]={0,0,0,0,0,0,0,0}; for(int i=0;i

贪心算法实验报告

福建工程学院计算机与信息科学系 实验报告 1 2 3 4 5 篇二：北邮算法作业贪心算法实验报告 第三次算法作业（贪心算法） 姓名：吴迪 班级：08211312 学号：08211488 班内序号 15 摘要：本文为完成作业problem1，problem3，problem4，problem5的四道贪心算法题。 备注：所有后缀为_ex的可执行文件为文件输入输出模式的程序，比如problem1_ex.exe （所有算法实现代码承诺为本人自己编写并且截图为实际有效截图，所有程序均通过 dev-c++编译器实际测试可以运行） problem 1 特殊的01背包（原算法分析题4-3） 问题描述：01背包是在n件物品取出若干件放在空间为c的背包里，每件物品的体积为 w1，w2??wn，与之相对应的价值为p1,p2??pn，并取得最大价值。普通的01背包中物品的重 量和价值没有明确的关系，这里定义一种特殊的01背包：向背包中放入的物品的价值和体积 成反比，也就是价值越高，体积越小，注意这里物品价值和体积的乘积并不是固定值。例如： 如下的物品满足这 个“特殊的01背包”,5件物品: 物品1,价值 v=6,体积w=20 物品2,价值 v=1,体积w=60 物品3,价值 v=20,体积w=3 物品4,价值 v=15,体积w=15 物品5,价值 v=99,体积w=1 假如我有一个容量为c的背包,c=20，那么选择物品3、4、5可以获得最大价值134。 输入：首先是一个整数t,代表测试数据的组数。每组测试数据首先是两个正整数n和c， n代表物品的个数，c代表背包的最大容积。然后有n行整数，每行有两个整数，分别代表物 品的价值v和体积w。t的范围是(1-100),n的范围是(1-100000),c、v、w的范围不超过四字 节的int型。 输出：首先输出测试数据的组号，例如第一组的组号为“case 1:”，占一行。然后是一 个整数，代表可以取得的最大价值，占一行。 sample input: 5 5 20 6 20 1 60 20 3 15 15

java实现贪心算法中的多机调度

package com.test; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Scanner; public class Duojidiaodu { public static void main(String[] args) { // TODO Auto-generated method stub BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); try { System.out.println("请输入机器个数："); int jiqigeshu=Integer.parseInt(br.readLine()); System.out.println("请输入作业个数："); int zuoyegeshu=Integer.parseInt(br.readLine()); Start start=new Start(jiqigeshu, zuoyegeshu);//指明有几台机器以及几道作业 start.show();//显示每台机器都有哪些作业 } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); }finally{ if(br!=null) try { br.close(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } } } } class JiqiManger{ ArrayList al=new ArrayList(); public void addjiqi(Jiqi jiqi) { this.al.add(jiqi); } public Jiqi getjiqi(int id) { for(int i=0;i