johnson算法谁能介绍下 n-最短路径 的算法

工件加工顺序问题（约翰逊法）

最小工时是2,是工件A在设备1的,按规则,A先加工; 去除A后,BCDE中 最小工时是3,工件B和D在设备1和2,设取B先加工,D最后加工 去除ABD后,CE中 最小工时是4,工件E在设备2,E最后加工 因此加工顺序为: ABCED 总计加工周期为25

ford-johnson algorithm是什么算法

算法是用来解决一个问题的程序或者公式。

“算法”（algorithm）这个词源自生活在公元9世纪的波斯数学家Al-Khowarizmi。

一个电脑程序可以被看成是一个精心设计的算法。

在数学和电脑学科，一个算法通常意味着一个可以解决循环问题的小程序。

width="295" height="33" usemap="#MapMap2Map" border="0">

<生产与运作管理> Palmer法，关键工件法，CDS法三者的比较分析

（一）Palmer法 1965年D.S.Palmer（帕尔玛）提出按斜度指标排列工件的启发式算法， 称之为Palmer法。

工件的斜度指标可按下式计算： k=1，2，……，m m：表示机器数； ：表示工件i在Mk上的加工时间。

按照各工件 不增的顺序排列工件，可得出令人满意的顺序。

Palmer法可以结合下例来理解： ik Palmer法的理解例11.3 不增的顺序排列工件，得到加工顺序（1，2，3，4）或（2，1，3，4），恰好，这两个顺序都是最优顺序。

如不是这样，则从中挑选较优者。

在最优顺序下，F max =28。

例11.3 有一个4/3/F/Fmax 问题，其加工时间如表11-5所示，用Palmer法求解。

-1表11-5 加工时间矩阵 （二）关键工件法关键工件法是一个启发式算法，其步骤如下： （1）计算每个工件的总加工时间 ，找出加工时间最长 的工件C（j＝m），将其作为关键工件。

（2）对于余下的工件，若 ，则按不减的顺序排成一 个序列S ，则按不增的顺序排列成一个序列S ）即为所求顺序。

例题 下面用关键工件法求例11．3的近优解。

求P 如表11-6所示。

求解如下。

表11-6用关键工序法求解 1311 16 14 总加工时间最长的为3号工件； （三）CDS法Campbell，Dudek，Smith（康坎贝尔、杜得克、史密斯）三人提出了一 个启发式算法，简称CDS法。

CDS法把Johnson算法用于一般的n/m/P/Fmax 问题，得到（m-1）个加工顺序，取其中优者。

具体做法是，对加工时间 ＝1，2，…，m-1，用Johnson算法求（m-1）次加工顺序，取其中最好的结果。

约翰逊排序法怎么计算总工期

根据约翰逊（S.M.Johson）—贝尔曼（R.Bellem）法则的基本思想：在TiA和TiB中找到最小对应的的工序，若为先行工序则排在最前，若为后续工序则排在最后。

找出一个任务后，任务数量减少一项，在剩余的m-1项任务（施工段）中仍采用上述方法进行排序，以此类推直到剩余的任务数为0，最终得到的就是最优施工顺序。

【例题】某工程队拟对相邻的两座小桥的基础工程进行施工，按工程队的机具设备等施工能力，经计算求得各个小桥的挖基和砌筑基础工序的持续时间（日）如表1-1所列，试确定其施工总工期最短的施工顺序。

排序方法：从表1-1中可以看出，t2B=1d是最小的，且为2号桥的后续工序，故2号桥放在最后施工。

删去这个任务后，胜于的4项任务中，t5A=2d为最小值，且是五号桥的先行工序，故5号桥放在最先施工。

以此类推最后得到的最佳施工顺序为：5号、1号、4号、3号、2号。

然后，按排定的顺序绘制横道图（1-2），其总工期为25d。

谁能介绍下 n-最短路径 的算法

最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

算法具体的形式包括： 确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。

确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。

在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。

全局最短路径问题 - 求图中所有的最短路径。

用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。

最常用的路径算法有： Dijkstra算法 A*算法 Bellman-Ford算法 Floyd-Warshall算法 Johnson算法 所谓单源最短路径问题是指：已知图G＝（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。

首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。