当前位置:编程学习 > C#/ASP.NET >>

[编程难题]编写一个求解时间满足约束的的算法.说明内详.真诚求助

1/已知
有如下一组活动,每个活动都有其工作时间和所需人力,在保证活动前后顺序和不超过人力资源约束的前提下,求得所有活动完成的总共最短工作时间.

已知参数如下: 
说明:活动序号j ,工作时间pj ,所需人力lj ,前序活动Lj ,优先权v(j)

活动的优先权:
j   1  2  3 4 5 6 7 8 9 10 11
v(j)10 11 7 9 3 8 5 4 6 2  1
总的人力资源约束maxReaource为常量 6 ,指的是同时工作的人力数量不能超过此常量
以上数据和人力资源约束常量均为已知,活动序号不表示活动的执行顺序.
2/求解
假设为每个活动随机分配一个不重复的正整数为活动优先权,在两活动竞争执行位置时优先权高的竞争到此位置.(如活动2,3竞争执行时,由于活动3的优先权6>活动2的优先权5,所以3执行)
说明:求得结果应该如下图

j节点下标;
s-正在处理下标
v(j)活动j的优先权
j* s中最大的优先权的活动
s 已排序活动



最后一个活动的结束时间为25
 
3/算法:
输入:节点的先后顺序,优先权,所需人力,工作时间
输出:最后一个活动的结束时间
begin
int m=10;//活动的数量
Task[] processing = new Task[m];//正在处理活动集合
Task[] scheduled = new Task[m]; //已排序活动集合
int startTime = 0;//初始化活动开始时间
int finishTime = 0;// 初始化活动结束时间
int j=0;//活动下标
int maxReaource =6;
while(j<m)do
把后序节点加入正在处理活动集合;
选择此集合中优先权最大的一个活动;
活动j的最早开始时间为它所有前序任务的最晚完成时间;
活动j的开始时间为最小的f,f满足
(1)最早开始时间<=f 
   (2)在时间l内可用资源数量<=maxHead(所需人力)
    l=f,f+1,…f+processing_time;
活动j的结束时间为它的开始时间+它的处理时间;
将此活动加入到已排序活动集合中;
在正在处理活动集合中删除此活动;
j=j+1;
end
output 最后一个活动的完成时间
end 
 
4/一些定义:
活动类定义如下:
public class Task
{
private int _task_id;
       private string _task_name;
       private int _rpoject_id;
       private int _task_type;
       private int _task_lines;
        private int _processing_time;
        private int _max_head;
        private Task[] _pre_tasks;
        private int _priority;
        private int _employee_id;
        private int _cost_on_task;
        private int _start_time;
        private int _finish_time;
}
 
public class Task_pre
{
       private int _task_id;
   private int _task_pre_id;
}
以上两个类的数据都保存在SQLServer数据库的数据表之中


--------------------编程问答-------------------- 迷糊,顶 --------------------编程问答-------------------- 看着就有点迷!
帮顶吧。 --------------------编程问答-------------------- 用树呢
帮顶下 --------------------编程问答-------------------- 的确是复杂了点,但是很有挑战,也挺有难度,还恳请高手指教 --------------------编程问答-------------------- google "图的宽度优先搜索".

也就是用一个队列, 依次遍历同层节点. --------------------编程问答-------------------- 何不转换成立体几何?
最后求得是体积,也就是时间了
--------------------编程问答-------------------- 怎么感觉有点运筹学的意思?
有点像优化,
都忘了。。。 --------------------编程问答-------------------- 路由上的 寻址算法

叫做最小红点集算法。 --------------------编程问答-------------------- 代码嘛,自己写咯。。 --------------------编程问答-------------------- 老王 就是算法不会写 才请教的 
我是初学者 还请多指教 --------------------编程问答-------------------- shrinerain google "图的宽度优先搜索". 

路由上的 寻址算法 叫做最小红点集算法。

你们能提供更详细些的说明吗? 多谢
补充:.NET技术 ,  C#
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,