一调度算法问题 (100分)

在天津港引航站的生产过程中的一引水员调度问题：
1、引航站接收局调度发出的24小时的船舶动态，一天发生动态的时间 7：00（进） 9：00（出） 11：00（进） ......每两小时有进港动态、再两小时有出港动态……（不是每批进港和出港所用的时间小于2小时）
2、引航站有n个引水员、一天接收m条船舶动态（不能说m条船，这里有m条船次的概念，因为有的船在码头上停很短的时间）（n>m），派其中的若干名引水员到船上引水，原则上一船一名引水员；船舶按长宽分1、2、3级，引水员分1、2、3级，其中1级引水员能引所有的船，2级引水员能引2、3级船、3级引水员只能引3级船；
3、考虑过船（即引出船时，引进新船），但天津港的航道有自己的特点，除有较多的海港码头外，还有一些内河码头(海河的入海口和天津港相连)，需过一些船闸、桥梁。这样不同的泊位地点、不同的时间需要不同的约束条件来考虑过船。“引水”需要的时间：由港口到达锚地需要1.5小时,
过船按出发地点的远近分四种情况：
1）、新港： 07:00 to 08:30：找临近点儿且止时间为4小时之内的动态，如果没有，则找在找7.5小时之内的动态；
08:31 to 18:30：找临近点儿且止时间为4小时之内的动态，如果没有，再找18:30之内的动态；
其他时间：找临近点儿且止时间为4小时之内的动态。
2）、过船闸：06:30 之前：找计划时间10：00之前且止时间为4.5小时之内的动态；
06:30 to 07:59：找计划时间14：30之前且止时间为4.5小时之内的动态；
08:00 to 15:59：找计划时间18:30之前且止时间为4.5小时之内的动态；
16:00 ：找计划时间22：00 之前且止时间为4.5小时之内的动态；
3）、过桥：06:30 之前：找计划时间10：00之前且止时间为5小时之内的动态；
06:30 to 07:59：找计划时间14:30小时之前且止时间为5小时之内的动态；
08:00 to 15:59：找计划时间18:30之前且止时间为5小时之内的动态；
15:30 ：找计划时间22：00 之前且止时间为5小时之内的动态；
4）、更远：不考虑过船
4、另外，还有一些条件考虑公休、假期、不能连续夜班等。
大夜班：22：00 - 6：00
小夜：20：00之后返回的
小夜班不能连大夜班，大夜班不能连大夜班。
注意引水员的假期是一段时间，在此假期之外的时间，而且该引水员在此轮排班中可以安排上船。
5、决策目标：找出一满意解，使得所用工时较少并且兼顾所有引水员。

太花时间了，
还是自己想吧！

朋友们，我是说您有何高见？用什么算法可解？如何建数学模型？

不行了，头晕掉了。
>找出一满意解
能不能先写出一个找出合理解的算法？
（我看要用产生式系统了...）

把题目发给我：brute@21cn.com，有空我研究一下。

使用遗传算法吧：
从本世纪40年代起,生物模拟构成了计算科学的一个组成部分。近三
十年来,计算机学者对模拟自然过程的浓厚兴趣和研究,形成了今天的一个
交叉研究领域——进化算法(Evolutionary Algorithm, EA)。它是一类用
机器模拟自然过程来求解复杂问题的随机搜索算法(或称为问题求解方法)
。生物体所面临的问题以混沌、随机、瞬间和非线性为典型特征。遗传算
法(Genetic Algorithms, GAs)只是进化算法的一种,它主要是对生物界自
然选择和自然遗传机制进化过程的模拟,如借鉴达尔文进化论中的"适者生
存,不适应者淘汰"观点等,而且是在分子水平级上的模拟。遗传算法最初由
美国的J.H Holland 提出,但当时是为自适应系统设计的一般框架,后来由
De Jong, J. Grefenstette, L. Davis和D. Goldberg等人进行了大量的
改进,使遗传算法应用于更广泛的范围。KOZA则将GA扩充到程序设计形成
了遗传程序设计(Genetic Programming, GP),成为遗传算法的一个非常重
要的分支,并为自动程序设计提供了一种有效途径。
目前,遗传算法作为一种实用和健壮的优化和搜索方法,已应用到许多
领域,如:并行与分布式系统中的任务平衡与调度、网络中的路由选择、大
规模集成电路的设计、策略规划、基因合成、机器学习、问题优化、经济
规划以及解决一些NP困难问题等。

二、 遗传算法框架
在遗传算法中,将问题的求解的过程,看成一个在候选解空间寻找满足
问题要求的解或近似解的搜索过程。遗传算法的重点在适应规划和适应度
量方面。遗传算法的适应规划用于指导算法怎么样在空间进行搜索,一般
采用遗传算子(或称遗传操作)诸如交配(Crossover)和变异(Mutation)等,
以及模拟自然过程的选择机制,而适应度量采用计算适应值的方法来评估
一个候选解的优劣。
遗传算法求解问题的过程如下:
1. 首先生成一组初始的候选解群体(假设为M个候选解个体),称为第
0代;
2. 计算群体中各个候选解的适应值;
3. 如果有候选解满足算法终止条件,算法终止,否则继续4;
4. 根据交配概率,将候选解群体中的个体随机两两配对,进行交配操
作以生成新的候选解;
5. 根据变异概率,对4中生成的候选解群中的每个个体进行变异操作;
6. 使用选择机制形成新一代候选解;转2。
从上面的算法过程中,我们可以知道,用遗传算法来求解问题有四个基
本要素:1候选解的表示方式;2适应值的定义及度量方法;3算法的控制参数
与变量;4算法终止准则。
候选取解的表示方式,最简单的就是采用定长二进制编码。如我们可
以将十进制的40转换成二进制的串,(40)10=(101000)2,反过来就可以将一
个二进制串解码为一个十进制整数。
适应值的定义及度量方法与要解决的问题有关,通常用目标函数来评
估候选取解的优劣。
算法的控制参数与变量。通常,我们把每一代中的候选解个数M称为群
体规模,群体规模M在整个算法中一般是不变的一个常数。遗传操作主要是
杂交和变异两个算子,并有其相应的概率参数(Pc:杂交概率,Pm变异概率)
来进行控制。遗传算法求解问题时,并不保证能找到满足问题要求的解,所
以,还要设定算法的最大迭代次数(或称为代数)。
算法终止准则一般有:找到了满足问题的解;候选取群体已收敛于某一
点;算法已达到了设定的代数等。
这样,一个简单遗传算法的框架可非形式化地表示如下:
Simple_Genetic_algorithm(){
t:=1;
/*变量t表示迭代代数*/
初始化候选解群体Population(t);
计算各个解的适应值;
do
while(终止条件不满足)
{
随机地将群中的个体两两配对,进行交配操作;
执行变异操作;
利用选择机制形成下一代候选取opulation(t+1):=Selection(Population(t));
t:=t+1;
}
}
...........

to wtang:
请问您有遗传算法的源程序吗？
mail to me: liuym@tianjinport.ptacn.com
thanks a lot.

到这里看一看,有你需要的资料和相应的原码
http://master.chinaren.net/~sinokdd/

to Chenlili:
题目就在上面呀！！！！！

如果你累了，可以一边歇会儿；
别烦我；

嘿嘿,这周就考数学模型

我帮你提前

同志们，该问题的实际情况，比我上面写的还要复杂得多。
有兴趣吗？我把该问题全部贴出来。

你的问题已经过期，请自己提前或结束，谢谢

多人接受答案了。