幽幽学子 2008-10-8 16:57
高手请进------请教贪心法处理多机调度问题...
[color=red][font=宋体][size=12pt][b]征求完整C语言[/b][/size][/font][font=宋体][size=12pt][b]代码????[/b][/size][/font][/color]
[font=宋体][size=12pt][b]要求[/b]:[/size][/font]
[font=宋体][size=12pt] 给出一种作业调度方案，使所给的[/size][/font][size=12pt]n[/size][font=宋体][size=12pt]个作业在尽可能短的时间内由[/size][/font][size=12pt]m[/size][font=宋体][size=12pt]台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。[/size][/font]
[font=宋体][size=12pt][font=宋体][size=12pt][b]提示:[/b][/size][/font][/size][/font][font=宋体][size=12pt][font=宋体][size=12pt]
[size=12pt][font=Times New Roman]1[/font][/size][font=宋体][size=12pt]、把作业按加工所用的时间从大到小排序[/size][/font][size=12pt][/size]
[size=12pt][font=Times New Roman]2[/font][/size][font=宋体][size=12pt]、如果作业数目比机器的数目少或相等，则直接把作业分配下去[/size][/font][size=12pt][/size]
[size=12pt][font=Times New Roman]3[/font][/size][font=宋体][size=12pt]、[/size][/font][size=12pt][font=Times New Roman] [/font][/size][font=宋体][size=12pt]如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上[/size][/font][size=12pt][font=Times New Roman]s[/font][/size][font=宋体][size=12pt]最小的链表加入新作业。[/size][/font][size=9pt][/size]
[size=9pt][font=Times New Roman]typedef struct Job[/font][/size]
[size=9pt][font=Times New Roman]{[/font][/size]
[size=9pt][font=Times New Roman] int ID;//[/font][/size][font=宋体]作业号[/font][size=9pt][/size]
[size=9pt][font=Times New Roman] int time;//[/font][/size][font=宋体]作业所花费的时间[/font][size=9pt][/size]
[size=9pt][font=Times New Roman]}Job;[/font][/size]
[size=9pt][font=Times New Roman][/font][/size]
[size=9pt][font=Times New Roman]typedef struct JobNode //[/font][/size][font=宋体]作业链表的节点[/font][size=9pt][/size]
[size=9pt][font=Times New Roman]{[/font][/size]
[size=9pt][font=Times New Roman] int ID; [/font][/size]
[size=9pt][font=Times New Roman] int time;[/font][/size]
[size=9pt][font=Times New Roman] JobNode *next;[/font][/size]
[size=9pt][font=Times New Roman]}JobNode,*pJobNode;[/font][/size]
[size=9pt][font=Times New Roman][/font][/size]
[size=9pt][font=Times New Roman]typedef struct Header //[/font][/size][font=宋体]链表的表头[/font][size=9pt][/size]
[size=9pt][font=Times New Roman]{[/font][/size]
[size=9pt][font=Times New Roman] int s;[/font][/size]
[size=9pt][font=Times New Roman] pJobNode next;[/font][/size]
[size=9pt][font=Times New Roman]}Header,pHeader;[/font][/size]
[size=9pt][font=Times New Roman][/font][/size]
[font=Times New Roman][size=9pt]int SelectMin(Header* M,int m)[/size]
[size=9pt]{[/size]
[size=9pt] int k=0;[/size]
[size=9pt] for(int i=1;i<m;i++)[/size]
[size=9pt] {[/size]
[size=9pt] if(M[i].s<m[k].s)k=i;[/size]
[size=9pt] }[/size]
[size=9pt] return k;[/size]
[size=9pt]}[/size]
[/font][/size][/font][/size][/font][/i]
[[i] 本帖最后由 幽幽学子 于 2008-10-8 16:58 编辑 [/i]]