精华内容
下载资源
问答
  • 该程序(cpm)是关键路径法算法的实现,该算法可以以最小的总成本和最佳的持续时间来计划一组项目活动。 建筑学 核心组件是cpm.py模块。 该模块实现了关键路径方法算法,旨在用作库。 有两个使用cpm.py模块的用户...
  • 关键路径法中,一般有以下一些时间参数: 最早开始时间(Early Start)活动最早开始时间由所有前置活动中最后一个最早结束时间确定。 最早结束时间(Early Finish)活动的最早结束时间由活动的最早开始时间...
    基本概念:
    在关键路径法中,一般有以下一些时间参数:

    最早开始时间(Early Start)活动最早开始时间由所有前置活动中最后一个最早结束时间确定。

    最早结束时间(Early Finish)活动的最早结束时间由活动的最早开始时间加上其工期确定。

    最迟结束时间(Late Finish)一个活动在不耽误整个项目的结束时间的情况下能够最迟开始的时间。它等于所有紧后工作中最早的一个最晚开始时间。

    最迟开始时间(Late Start)一个活动在不耽误整个项目的结束时间的情况下能够最早开始的时间。它等于活动的最迟结束时间减去活动的工期。

    总时差(Total Float) 指一项活动在不影响整体计划工期的情况下最大的浮动时间。

    自由时差(Free Float)指活动在不影响其紧后工作的最早开始时间的情况下可以浮动的时间。

    *
    *
    算法原理-前导图(PDM)法:
    对于活动的最早开始和最早结束时间,采用正推法计算,其算法如下所示:

    1.将第一个活动的最早开始时间设置为1.

    2.在活动的最早开始时间上加上其工期,得到活动的最早结束时间。

    3.根据该活动与后置活动的逻辑关系,计算后置活动应该的最早开始时间,并与其已有的最早开始时间对比,如果其后置活动还没有设置最早开始时间,则将此时间设为其最早开始时间,如果此时间早于其后置活动已有的最早开始时间,则保留后置活动的原有最早开始时间,如果此时间迟于其后置活动已有的最早开始时间,则将此时间设置为后置活动的最迟开始时间。

    4.重复步骤2和3,直到所有活动的时间被计算完为止。

    对于以上所示的最早时间的计算过程,可以以公式的形式表示如下:

    当活动间的逻辑关系为SS,则计算如下

    ESj=max{ ESi + STS}

    当活动间的逻辑关系为FS,则计算如下

    ESj= max{ESi+ Di+ FTS}

    当活动间的逻辑关系为FF,计算如下

    ESj= max{ESi+ Di - Dj +FTF}

    当活动间的逻辑关系为SF,计算如下

    ESj=max{ ESi - Dj +STF}

    在计算出各个活动的最早开始和结束时间之后,就可以计算活动的自由时差,在计算前导图(PDM)的自由时差时应注意,由于引入了多种逻辑关系,并且活动间可以存在延时,所以其计算方法与箭线图(ADM)的计算方法不一样。

    对于前导图(PDM)的活动间,除了延时还可以存在时间间隔(LAG),一般可以按照下面的方式计算。

    当活动间的逻辑关系为SS,则计算如下

    LAGi-j= ESj- ESi- STS

    当活动间的逻辑关系为FS,则计算如下

    LAGi-j= ESj- EFi- FTS

    当活动间的逻辑关系为FF,计算如下

    LAGi-j= EFj- EFi- FTF

    当活动间的逻辑关系为SF,计算如下

    LAGi-j= EFj- ESi- STF

    则对于任意一个活动,其自由时差为

    FFi=min{ LAGi-j}

    最后一个活动的自由时差为0.

    对于总时差,终点节点的总时差为0,对于其它任意一个节点,总时差按照下式进行计算

    TFi=min{TFj+ LAGi-j}

    对于任意一个活动的最晚开始时间可以由其最早开始时间加上总时差得到,同样,其最晚开始时间可以由最早结束时间加上其总时差得到,公式表示如下

    LSi=ESi+TFi

    LFi=EFi+TFi



    package com.ryan.activity;

    import java.util.LinkedList;
    import java.util.List;

    /**
    * TASK基础类
    *
    * @author ryan
    */
    public class Task {
    private String taskNumber;//任务编号
    private String logic;//任务之间的逻辑关系

    private double earlyStartTime;//最早开始时间
    private double earlyFinishTime;//最早结束时间
    private double lateStartTime;//最晚开始时间
    private double lateFinishTime;//最晚结束时间
    private double dut;//执行时间
    private double delayTime;//延迟时间
    private double slack;//机动时间

    private String[] logicArray;//任务之间的逻辑关系
    private double[] earlyStartTimeArray;//最早开始时间
    private double[] earlyFinishTimeArray;//最早结束时间
    private double[] lateStartTimeArray;//最晚开始时间
    private double[] lateFinishTimeArray;//最晚结束时间
    private double[] dutArray;//执行时间
    private double[] delayTimeArray;//延迟时间
    private double[] slackArray;//机动时间

    private boolean isCalEST = false;//是否计算了最早开始时间
    private boolean isCalEFT = false;//是否计算了最早结束时间
    private boolean isCalLST = false;//是否计算了最晚开始时间
    private boolean isCalLFT = false;//是否计算了最晚结束时间
    private boolean isCalSlack = false;//是否计算了机动时间

    private boolean isCalETArray = false;//是否计算了最早开始时间
    private boolean isCalLTArray = false;//是否计算了最晚开始时间
    private boolean isCalSlackArray = false;//是否计算了机动时间

    private boolean isCriticalPath = false;//是否是关键路径

    private List<Task> previousTasks = new LinkedList<Task>();//前置任务集合
    private List<Task> nextTasks = new LinkedList<Task>();//后置任务集合

    /*
    * 计算最早开始时间
    */
    public void calculateET(){
    if(!this.isCalEST()){
    double est = 0.0d;//临时存放最早开始时间
    boolean isTmp = false;//标记是否执行了逻辑关系中的代码
    if(this.getPreviousTasks().size()==0){//第一个任务是没有前置任务的,所以其最早开始时间是0
    this.earlyStartTime = est;
    this.isCalEST = true;
    } else {
    if("FS".equals(logic)){//ES= max{ES(前)+ Dur(前)+ FTS}
    for(Task previousTask : this.getPreviousTasks()){
    if(previousTask.getEarlyFinishTime()>est && previousTask.isCalEFT()){

    est = previousTask.getEarlyFinishTime();
    isTmp = previousTask.isCalEFT();
    }
    }
    est = est + this.getDelayTime();
    }else if("FF".equals(logic)){//ES= max{ES(前)+ Dur(前) - Dur +FTF}
    for(Task previousTask : this.getPreviousTasks()){
    if(previousTask.getEarlyFinishTime()>est && previousTask.isCalEFT()){
    est = previousTask.getEarlyFinishTime();
    isTmp = previousTask.isCalEFT();
    }
    }
    est = est + this.getDelayTime() - this.getDut();
    }else if("SS".equals(logic)){//ES=max{ ES(前) + STS}
    for(Task previousTask : this.getPreviousTasks()){
    if(previousTask.getEarlyStartTime()>est && previousTask.isCalEST()){
    est = previousTask.getEarlyStartTime();
    isTmp = previousTask.isCalEST();
    }
    }
    est = est + this.getDelayTime();
    }else if("SF".equals(logic)){//ES=max{ ES(前) - Dur +STF}
    for(Task previousTask : this.getPreviousTasks()){
    if(previousTask.getEarlyStartTime()>est && previousTask.isCalEST()){
    est = previousTask.getEarlyStartTime();
    isTmp = previousTask.isCalEST();
    }
    }
    est = est - this.getDut() + this.getDelayTime();
    }
    if(isTmp){
    this.earlyStartTime = est;
    this.isCalEST = true;
    }
    }
    }
    if(!this.isCalEFT() && this.isCalEST()){
    this.earlyFinishTime = this.getEarlyStartTime() + this.getDut();
    this.isCalEFT = true;
    }
    }

    /*
    *计算最晚时间
    */
    public void calculateLT(){
    if(!this.isCalLST()){
    calculateLT(this.nextTasks,this);
    }
    if(!this.isCalLFT()){
    calculateLT(this.nextTasks,this);
    }
    }


    /*
    * task的后置任务nextTasks
    */
    public void calculateLT(List<Task> nextTasks,Task task){
    double tmpSlack = 0.0d;//临时时间差
    boolean isTmp = false;//标记
    if(nextTasks.size()==0 ){
    if(task.isCalEST() && task.isCalEFT()){
    task.lateFinishTime = task.getEarlyFinishTime();
    task.slack = 0.0d;
    task.isCalLFT = true;
    task.isCalSlack = true;
    task.lateStartTime = task.getEarlyStartTime();
    task.slack = 0.0d;
    task.isCalLST = true;
    task.isCalSlack = true;
    }
    } else{
    for(int i = 0; i<nextTasks.size(); i++){
    Task nextTask = nextTasks.get(i);
    if(!nextTask.isCalLFT())
    return;
    if(!nextTask.isCalLST())
    return;
    if(nextTask.isCalSlack){
    double _tmp = tmpSlack;//临时时间间隔
    if("FS".equals(nextTask.logic) && nextTask.isCalEST() && task.isCalEFT()){//Slack = min{slack后+ES后-EF-FTS}
    _tmp = nextTask.getSlack() + nextTask.getEarlyStartTime() - task.getEarlyFinishTime() - nextTask.getDelayTime();
    isTmp = true;
    }else if("FF".equals(nextTask.logic) && nextTask.isCalEFT() && task.isCalEFT()){//Slack = min{slack后+EF后-EF-FTF}
    _tmp = nextTask.getSlack() + nextTask.getEarlyFinishTime() - task.getEarlyFinishTime() - nextTask.getDelayTime();
    isTmp = true;
    }else if("SF".equals(nextTask.logic) && nextTask.isCalEFT() && task.isCalEST()){//Slack = min{slack后+EF后-ES-STF}
    _tmp = nextTask.getSlack() + nextTask.getEarlyFinishTime() - task.getEarlyStartTime() - nextTask.getDelayTime();
    isTmp = true;
    }else if("SS".equals(nextTask.logic) && nextTask.isCalEST() && task.isCalEST()){//Slack = min{slack后+ES后-ES-STS}
    _tmp = nextTask.getSlack() + nextTask.getEarlyStartTime() - task.getEarlyStartTime() - nextTask.getDelayTime();
    isTmp = true;
    }
    if(i==0){
    tmpSlack = _tmp;
    }
    if(_tmp < tmpSlack ){
    tmpSlack = _tmp;
    }
    }
    }

    }
    if(isTmp && task.isCalEST() && task.isCalEFT()){//isTmp标记为true,说明已经经过计算。
    task.lateFinishTime = task.getEarlyFinishTime() + tmpSlack;
    task.setSlack(tmpSlack);
    task.isCalLFT = true;
    task.isCalSlack = true;
    task.lateStartTime = task.getEarlyStartTime() + tmpSlack;
    task.setSlack(tmpSlack);
    task.isCalLST = true;
    task.isCalSlack = true;

    }
    }

    /*
    * 计算最早开始和最早结束时间
    * */
    public void calculateETArray(){
    if(!this.isCalETArray()){
    double[] dutArray = this.getDutArray();
    double[] delayTimeArray = this.getDelayTimeArray();
    String[] logicArray = this.getLogicArray();
    double[] earlyStartTimeArray = new double[dutArray.length];
    double[] earlyFinishTimeArray = new double[dutArray.length];
    int ETCount = 0;
    for (int i=0;i<dutArray.length;i++) {
    this.setDelayTime(delayTimeArray[i]);
    this.setLogic(logicArray[i]);
    this.setDut(dutArray[i]);
    this.calculateET();
    earlyStartTimeArray[i] = this.getEarlyStartTime();
    earlyFinishTimeArray[i] = this.getEarlyFinishTime();
    ETCount++;

    }
    if(ETCount==dutArray.length){
    this.setEarlyStartTimeArray(earlyStartTimeArray);
    this.setEarlyFinishTimeArray(earlyFinishTimeArray);
    this.setCalETArray(true);
    }
    }
    }
    /*
    * 计算最晚开始和最晚结束时间
    * */
    public void calculateLTArray(){
    if(!this.isCalLTArray()){
    double[] dutArray = this.getDutArray();
    double[] delayTimeArray = this.getDelayTimeArray();
    String[] logicArray = this.getLogicArray();
    double[] lateStartTimeArray = new double[dutArray.length];
    double[] lateFinishTimeArray = new double[dutArray.length];
    int LTCount = 0;
    for (int i=0;i<dutArray.length;i++) {
    this.setDelayTime(delayTimeArray[i]);
    this.setLogic(logicArray[i]);
    this.setDut(dutArray[i]);
    this.calculateLT();
    lateStartTimeArray[i] = this.getLateStartTime();
    lateFinishTimeArray[i] = this.getLateFinishTime();
    LTCount++;
    }

    if(LTCount==dutArray.length){
    this.setLateStartTimeArray(lateStartTimeArray);
    this.setLateFinishTimeArray(lateFinishTimeArray);
    this.setCalLTArray(true);
    }
    }
    }

    /*
    * taskNumber 任务编号
    * logic 与前置任务的逻辑关系
    * dut 任务执行时间
    *delayTime 提前滞后时间
    */
    public Task(String taskNumber,String logic, double dut, double delayTime) {
    super();
    this.taskNumber = taskNumber;
    this.logic = logic;
    this.dut = dut;
    this.delayTime = delayTime;
    }

    /*
    * taskNumber 任务编号
    * logic 与前置任务的逻辑关系
    * dut 任务执行时间数组
    * delayTime 提前滞后时间数组
    */
    public Task(String taskNumber,String[] logicArray, double[] dutArray, double[] delayTimeArray) {
    super();
    this.taskNumber = taskNumber;
    this.logicArray = logicArray;
    this.dutArray = dutArray;
    this.delayTimeArray = delayTimeArray;
    }

    public String getTaskNumber() {
    return taskNumber;
    }

    public void setTaskNumber(String taskNumber) {
    this.taskNumber = taskNumber;
    }

    public double getDelayTime() {
    return delayTime;
    }

    public void setDelayTime(double delayTime) {
    this.delayTime = delayTime;
    }

    public double getDut() {
    return dut;
    }

    public void setDut(double dut) {
    this.dut = dut;
    }

    public double getEarlyFinishTime() {
    return earlyFinishTime;
    }

    public double getEarlyStartTime() {
    return earlyStartTime;
    }

    public double getLateFinishTime() {
    return lateFinishTime;
    }

    public double getLateStartTime() {
    return lateStartTime;
    }

    public double getSlack(){
    return slack;
    }

    public void setSlack(double slack){
    this.slack = slack;
    }

    public boolean isCalEST(){;
    return isCalEST;
    }

    public boolean isCalEFT(){;
    return isCalEFT;
    }

    public boolean isCalLST(){
    return isCalLST;
    }

    public boolean isCalLFT(){
    return isCalLFT;
    }

    public boolean isCriticalPath(){
    return isCriticalPath;
    }

    public List<Task> getPreviousTasks() {
    return previousTasks;
    }

    public String getLogic() {
    return logic;
    }

    public void setLogic(String logic) {
    this.logic = logic;
    }

    public void setPreviousTasks(List<Task> previousTasks) {
    this.previousTasks = previousTasks;
    for (Task task : this.previousTasks) {
    task.getNextTasks().add(this);
    }
    }


    public List<Task> getNextTasks() {
    return nextTasks;
    }

    public void setNextTasks(List<Task> nextTasks) {
    this.nextTasks = nextTasks;
    }

    public String[] getLogicArray() {
    return logicArray;
    }

    public void setLogicArray(String[] logicArray) {
    this.logicArray = logicArray;
    }

    public double[] getDelayTimeArray() {
    return delayTimeArray;
    }

    public void setDelayTimeArray(double[] delayTimeArray) {
    this.delayTimeArray = delayTimeArray;
    }

    public double[] getDutArray() {
    return dutArray;
    }

    public void setDutArray(double[] dutArray) {
    this.dutArray = dutArray;
    }

    public double[] getEarlyFinishTimeArray() {
    return earlyFinishTimeArray;
    }

    public void setEarlyFinishTimeArray(double[] earlyFinishTimeArray) {
    this.earlyFinishTimeArray = earlyFinishTimeArray;
    }

    public double[] getEarlyStartTimeArray() {
    return earlyStartTimeArray;
    }

    public void setEarlyStartTimeArray(double[] earlyStartTimeArray) {
    this.earlyStartTimeArray = earlyStartTimeArray;
    }

    public double[] getLateFinishTimeArray() {
    return lateFinishTimeArray;
    }

    public void setLateFinishTimeArray(double[] lateFinishTimeArray) {
    this.lateFinishTimeArray = lateFinishTimeArray;
    }

    public double[] getLateStartTimeArray() {
    return lateStartTimeArray;
    }

    public void setLateStartTimeArray(double[] lateStartTimeArray) {
    this.lateStartTimeArray = lateStartTimeArray;
    }

    public double[] getSlackArray() {
    return slackArray;
    }

    public void setSlackArray(double[] slackArray) {
    this.slackArray = slackArray;
    }


    public boolean isCalSlackArray() {
    return isCalSlackArray;
    }

    public void setCalSlackArray(boolean isCalSlackArray) {
    this.isCalSlackArray = isCalSlackArray;
    }

    public boolean isCalETArray() {
    return isCalETArray;
    }

    public void setCalETArray(boolean isCalETArray) {
    this.isCalETArray = isCalETArray;
    }

    public boolean isCalLTArray() {
    return isCalLTArray;
    }

    public void setCalLTArray(boolean isCalLTArray) {
    this.isCalLTArray = isCalLTArray;
    }

    public void setCriticalPath() {
    if(this.isCalLST() && this.isCalEST()){
    if(this.getLateStartTime()-this.getEarlyStartTime()==0)
    this.isCriticalPath = true;
    }
    }
    public void setCriticalPathArray() {
    if(this.isCalLTArray() && this.isCalETArray()){
    //TODO 待完成
    }
    }


    }




    还有一个封装测试类,利用随机数模拟蒙特卡洛模拟法(
    http://baike.baidu.com/view/2692033.htm


    package com.ryan.activity;

    import java.util.Iterator;
    import java.util.LinkedHashSet;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Random;
    import java.util.Set;

    /**
    * Task的计算逻辑类
    *
    * @author ryan
    */
    public class Wbs {
    private List<Task> tasks;//所有任务集合
    private Set<Task> noPreviousTasks;//没有前置任务的任务集合
    private Set<Task> noNextTasks;//没有后置任务的任务集合


    /**
    * @param tasks 所有任务集合
    * @return 没有前置任务的任务集合
    */
    public Set<Task> getNoPreviousTasks(List<Task> tasks){
    if(tasks!=null && tasks.size()>0){
    for(Task task : tasks){
    if(task!=null && task.getPreviousTasks().size()==0){
    this.noPreviousTasks.add(task);
    }
    }
    }
    return this.noPreviousTasks;
    }
    /**
    * @param tasks 所有任务集合
    * @return 没有后置任务的任务集合
    */
    public Set<Task> getNoNextTasks(List<Task> tasks){
    if(tasks!=null && tasks.size()>0){
    for(Task task : tasks){
    if(task!=null && task.getNextTasks().size()==0){
    this.noNextTasks.add(task);
    }
    }
    }
    return this.noNextTasks;
    }




    /**
    * @param tasks 所有任务
    * @return 没有前置任务计算完成之后,待计算的任务
    */
    private Set<Task> calculateNoPreviousEarlyTime(List<Task> tasks){
    // System.out.println("开始调用calculateNoPreviousEarlyTime(List<Task> tasks)------");
    Set<Task> calTasks = new LinkedHashSet<Task>();
    if(tasks!=null && tasks.size()>0){
    Set<Task> noPreviousTasks = this.getNoPreviousTasks(tasks);
    for(Task task : noPreviousTasks){
    // System.out.println("没有前置任务的是"+task.getTaskNumber());
    if(!task.isCalEST()&&!task.isCalEFT())
    task.calculateET();
    calTasks.add(task);
    }
    }
    // System.out.println("结束调用calculateNoPreviousEarlyTime(List<Task> tasks)------");
    return calTasks;
    }

    /**
    * @param nextTasks 本次待计算的任务
    * @return 下一次待计算的任务
    */
    public Set<Task> calculateEarlyTime(Set<Task> nextTasks){
    Set<Task> calTasks = new LinkedHashSet<Task>();
    if(nextTasks!=null && nextTasks.size()>0){
    Iterator<Task> it = nextTasks.iterator();
    while(it.hasNext()){
    Task task = it.next();
    // System.out.println("本次需要计算的任务是"+task.getTaskNumber());
    //找到本任务的前置任务看是不是全部计算完成了,
    List<Task> befTask = task.getPreviousTasks();
    //判断本任务的前置任务是不是完全计算完成的计数器
    int count = 0;//计数器
    for(int i=0;i<befTask.size();i++){
    Task bfTask = befTask.get(i);
    if(bfTask.isCalEST() && bfTask.isCalEFT())
    count++;
    }
    //如果全部计算完成,将本任务的后置任务加入到返回列表里
    if(count==befTask.size()){
    task.calculateET();
    // System.out.println("已经计算了"+task.getTaskNumber());
    calTasks.addAll(task.getNextTasks());
    //如果没有全部计算完成,把本任务加入到计算列表里
    }else{
    calTasks.add(task);
    }
    }
    }
    return calTasks;
    }

    /**
    * @param tasks 所有任务
    * @return 没有前置任务的下一层需要计算的任务
    */
    public Set<Task> calNoNextTasksLateTime(List<Task> tasks){
    Set<Task> calTasks = new LinkedHashSet<Task>();
    if(tasks!=null && tasks.size()>0){
    for (Task task : this.getNoNextTasks(tasks)) {
    if(!task.isCalLST()&&!task.isCalLFT())
    task.calculateLT();
    calTasks.add(task);
    }
    }
    return calTasks;
    }

    /**
    * @param nextTasks 本次待计算的任务
    * @return 下一次需要计算的任务
    */
    public Set<Task> calculateLateTime(Set<Task> nextTasks){
    Set<Task> calTasks = new LinkedHashSet<Task>();
    if(nextTasks!=null && nextTasks.size()>0){
    Iterator<Task> it = nextTasks.iterator();
    while(it.hasNext()){
    Task task = it.next();
    //找到本任务的后置任务看是不是全部计算完成了,
    List<Task> nextTask = task.getNextTasks();
    //判断本任务的后置任务是不是完全计算完成的计数器
    int count = 0;//计数器
    for(int i=0;i<nextTask.size();i++){
    Task ntTask = nextTask.get(i);
    if(ntTask.isCalLST()&&ntTask.isCalLFT())
    count++;
    }
    //如果全部计算完成,将本任务的后置任务加入到返回列表里
    if(count==nextTask.size()){
    task.calculateLT();
    // System.out.println("计算的是"+task.getTaskNumber());
    calTasks.addAll(task.getPreviousTasks());
    //如果没有全部计算完成,把本任务加入到计算列表里
    }else{
    calTasks.add(task);
    }
    }
    }
    return calTasks;
    }

    /*
    * 计算最早最晚时间
    */
    public void calculateTime() {
    //计算没有前置任务的任务
    Set<Task> firstTimes = calculateNoPreviousEarlyTime(this.tasks);
    //依次分层计算后一层的任务EST,EFT
    Set<Task> nextTimes = calculateEarlyTime(firstTimes);
    Set<Task> tmpTasks;
    do{
    tmpTasks = nextTimes;
    nextTimes = calculateEarlyTime(tmpTasks);

    }while(nextTimes.size()>0);

    firstTimes.clear();
    nextTimes.clear();
    tmpTasks.clear();
    //计算没有后置任务的任务
    firstTimes = calNoNextTasksLateTime(this.tasks);
    //依次分层计算后一层的任务的LST
    nextTimes = calculateLateTime(firstTimes);
    do{
    tmpTasks = nextTimes;
    nextTimes = calculateLateTime(tmpTasks);

    }while(nextTimes.size()>0);

    //打印计算结果
    for (Task task : this.tasks) {
    System.out.println(task.getTaskNumber()+"tnumber=="+task.getEarlyStartTime()+"est==="+task.getEarlyFinishTime()+"eft==="+task.getLateStartTime()+"lst==="+task.getLateFinishTime()+"lft===="+task.isCriticalPath());
    }
    }


    /**
    * @param tasks 所有任务
    * @return 没有前置任务计算完成之后,待计算的任务
    */
    private Set<Task> calculateNoPreviousEarlyTimeArray(List<Task> tasks){
    // System.out.println("开始调用calculateNoPreviousEarlyTime(List<Task> tasks)------");
    Set<Task> calTasks = new LinkedHashSet<Task>();
    if(tasks!=null && tasks.size()>0){
    Set<Task> noPreviousTasks = this.getNoPreviousTasks(tasks);
    for(Task task : noPreviousTasks){
    // System.out.println("没有前置任务的是"+task.getTaskNumber());
    if(!task.isCalETArray()){
    task.calculateETArray();
    System.out.println("计算了第一个"+task.getTaskNumber()+"tnumber=="+task.getEarlyStartTime()+"est==="+task.getEarlyFinishTime()+"eft===");

    calTasks.add(task);
    }
    }
    }
    // System.out.println("结束调用calculateNoPreviousEarlyTime(List<Task> tasks)------");
    return calTasks;
    }

    /**
    * @param nextTasks 本次待计算的任务
    * @return 下一次待计算的任务
    */
    public Set<Task> calculateEarlyTimeArray(Set<Task> nextTasks){
    Set<Task> calTasks = new LinkedHashSet<Task>();
    if(nextTasks!=null && nextTasks.size()>0){
    Iterator<Task> it = nextTasks.iterator();
    while(it.hasNext()){
    Task task = it.next();
    // System.out.println("本次需要计算的任务是"+task.getTaskNumber());
    //找到本任务的前置任务看是不是全部计算完成了,
    List<Task> befTask = task.getPreviousTasks();
    //判断本任务的前置任务是不是完全计算完成的计数器
    int count = 0;//计数器
    for(int i=0;i<befTask.size();i++){
    Task bfTask = befTask.get(i);
    if(bfTask.isCalETArray())
    count++;
    }
    //如果全部计算完成,将本任务的后置任务加入到返回列表里
    if(count==befTask.size()){
    task.calculateETArray();
    // System.out.println("已经计算了"+task.getTaskNumber());
    calTasks.addAll(task.getNextTasks());
    //如果没有全部计算完成,把本任务加入到计算列表里
    }else{
    calTasks.add(task);
    }
    }
    }
    return calTasks;
    }

    /**
    * @param tasks 所有任务
    * @return 没有前置任务的下一层需要计算的任务
    */
    public Set<Task> calNoNextTasksLateTimeArray(List<Task> tasks){
    Set<Task> calTasks = new LinkedHashSet<Task>();
    if(tasks!=null && tasks.size()>0){
    for (Task task : this.getNoNextTasks(tasks)) {
    if(!task.isCalLTArray())
    task.calculateLTArray();
    calTasks.add(task);
    }
    }
    return calTasks;
    }

    /**
    * @param nextTasks 本次待计算的任务
    * @return 下一次需要计算的任务
    */
    public Set<Task> calculateLateTimeArray(Set<Task> nextTasks){
    Set<Task> calTasks = new LinkedHashSet<Task>();
    if(nextTasks!=null && nextTasks.size()>0){
    Iterator<Task> it = nextTasks.iterator();
    while(it.hasNext()){
    Task task = it.next();
    //找到本任务的后置任务看是不是全部计算完成了,
    List<Task> nextTask = task.getNextTasks();
    //判断本任务的后置任务是不是完全计算完成的计数器
    int count = 0;//计数器

    for(int i=0;i<nextTask.size();i++){
    Task ntTask = nextTask.get(i);
    if(ntTask.isCalLTArray())
    count++;
    }
    //如果全部计算完成,将本任务的后置任务加入到返回列表里
    if(count==nextTask.size()){
    task.calculateLTArray();
    // System.out.println("计算的是"+task.getTaskNumber());
    calTasks.addAll(task.getPreviousTasks());
    //如果没有全部计算完成,把本任务加入到计算列表里
    }else{
    calTasks.add(task);
    }

    }
    }
    return calTasks;
    }

    /*
    * 计算最早最晚时间
    */
    public void calculateTimeArray() {
    //计算没有前置任务的任务
    Set<Task> firstTimes = calculateNoPreviousEarlyTimeArray(this.tasks);
    //依次分层计算后一层的任务EST,EFT
    Set<Task> nextTimes = calculateEarlyTimeArray(firstTimes);
    Set<Task> tmpTasks;
    do{
    tmpTasks = nextTimes;
    nextTimes = calculateEarlyTimeArray(tmpTasks);

    }while(nextTimes.size()>0);

    firstTimes.clear();
    nextTimes.clear();
    tmpTasks.clear();
    //计算没有后置任务的任务
    firstTimes = calNoNextTasksLateTimeArray(this.tasks);
    //依次分层计算后一层的任务的LST
    nextTimes = calculateLateTimeArray(firstTimes);
    do{
    tmpTasks = nextTimes;
    nextTimes = calculateLateTimeArray(tmpTasks);

    }while(nextTimes.size()>0);

    //打印计算结果
    for (int i =0; i<this.tasks.size();i++) {
    Task task = this.tasks.get(i);
    System.out.println(task.getTaskNumber()+"tnumber=="+task.getEarlyStartTimeArray()[0]+"est==="+task.getEarlyFinishTimeArray()[0]+"eft==="+task.getLateStartTimeArray()[0]+"lst==="+task.getLateFinishTimeArray()[0]+"lft");
    }
    }

    public List<Task> getTasks() {
    return tasks;
    }

    public void setTasks(List<Task> tasks) {
    this.tasks = tasks;
    }

    public Set<Task> getNoNextTasks() {
    return getNoNextTasks(tasks);
    }

    public Set<Task> getNoPreviousTasks() {
    return getNoPreviousTasks(tasks);
    }

    /*
    * tasks 所有任务集合
    */
    public Wbs(List<Task> tasks) {
    super();
    this.tasks = tasks;
    this.noNextTasks = new LinkedHashSet<Task>();
    this.noPreviousTasks = new LinkedHashSet<Task>();
    }

    public static void main(String args[]){
    // String[] l1 = {"FS"};
    // double[] d1 = {15};
    // double[] dl1 = {0};
    // Task t1 = new Task("1",l1,d1,dl1);
    // String[] l2 = {"FS"};
    // double[] d2 = {20};
    // double[] dl2 = {-5};
    // Task t2 = new Task("2",l2,d2,dl2);
    // String[] l3 = {"FS"};
    // double[] d3 = {26};
    // double[] dl3 = {0};
    // Task t3 = new Task("3",l3,d3,dl3);
    // String[] l4 = {"SS"};
    // double[] d4 = {18};
    // double[] dl4 = {10};
    // Task t4 = new Task("4",l4,d4,dl4);
    // String[] l5 = {"FS"};
    // double[] d5 = {15};
    // double[] dl5 = {0};
    // Task t5 = new Task("5",l5,d5,dl5);
    // String[] l6 = {"FS"};
    // double[] d6 = {38};
    // double[] dl6 = {0};
    // Task t6 = new Task("6",l6,d6,dl6);
    // String[] l7 = {"FS"};
    // double[] d7 = {25};
    // double[] dl7 = {-5};
    // Task t7 = new Task("7",l7,d7,dl7);
    // String[] l8 = {"FS"};
    // double[] d8 = {15};
    // double[] dl8 = {5};
    // Task t8 = new Task("8",l8,d8,dl8);
    // String[] l9 = {"SS"};
    // double[] d9 = {18};
    // double[] dl9 = {20};
    // Task t9 = new Task("9",l9,d9,dl9);
    // String[] l10 = {"FS"};
    // double[] d10 = {30};
    // double[] dl10 = {0};
    // Task t10 = new Task("10",l10,d10,dl10);
    // String[] l11 = {"FS"};
    // double[] d11 = {28};
    // double[] dl11 = {5};
    // Task t11 = new Task("11",l11,d11,dl11);
    // String[] l12 = {"FS"};
    // double[] d12 = {140};
    // double[] dl12 = {0};
    // Task t12 = new Task("12",l12,d12,dl12);
    // String[] l13 = {"FS"};
    // double[] d13 = {18};
    // double[] dl13 = {-5};
    // Task t13 = new Task("13",l13,d13,dl13);
    // String[] l14 = {"SS"};
    // double[] d14 = {20};
    // double[] dl14 = {10};
    // Task t14 = new Task("14",l14,d14,dl14);
    // String[] l15 = {"FS"};
    // double[] d15 = {15};
    // double[] dl15 = {0};
    // Task t15 = new Task("15",l15,d15,dl15);
    // String[] l16 = {"FS"};
    // double[] d16 = {33};
    // double[] dl16 = {0};
    // Task t16 = new Task("16",l16,d16,dl16);
    // String[] l17 = {"FS"};
    // double[] d17 = {8};
    // double[] dl17 = {0};
    // Task t17 = new Task("17",l17,d17,dl17);
    // String[] l18 = {"FS"};
    // double[] d18 = {15};
    // double[] dl18 = {0};
    // Task t18 = new Task("18",l18,d18,dl18);
    // String[] l19 = {"FS"};
    // double[] d19 = {17};
    // double[] dl19 = {0};
    // Task t19 = new Task("19",l19,d19,dl19);
    // String[] l20 = {"FS"};
    // double[] d20 = {25};
    // double[] dl20 = {0};
    // Task t20 = new Task("20",l20,d20,dl20);

    // Task t1 = new Task("1","FS",15,0);
    // Task t2 = new Task("2","FS",20,-5);
    // Task t3 = new Task("3","FS",26,0);
    // Task t4 = new Task("4","SS",18,10);
    // Task t5 = new Task("5","FS",15,0);
    // Task t6 = new Task("6","FS",38,0);
    // Task t7 = new Task("7","FS",25,-5);
    // Task t8 = new Task("8","FS",15,5);
    // Task t9 = new Task("9","SS",18,20);
    // Task t10 = new Task("10","FS",30,0);
    // Task t11 = new Task("11","FS",28,5);
    // Task t12 = new Task("12","FS",140,0);
    // Task t13 = new Task("13","FS",18,-5);
    // Task t14 = new Task("14","SS",20,10);
    // Task t15 = new Task("15","FS",15,0);
    // Task t16 = new Task("16","FS",33,0);
    // Task t17 = new Task("17","FS",8,0);
    // Task t18 = new Task("18","FS",15,0);
    // Task t19 = new Task("19","FS",17,0);
    // Task t20 = new Task("20","FS",25,0);
    //
    // List<Task> tl1 = new LinkedList<Task>();
    // List<Task> tl2 = new LinkedList<Task>();
    // List<Task> tl3 = new LinkedList<Task>();
    // List<Task> tl4 = new LinkedList<Task>();
    // List<Task> tl5 = new LinkedList<Task>();
    // List<Task> tl6 = new LinkedList<Task>();
    // List<Task> tl7 = new LinkedList<Task>();
    // List<Task> tl8 = new LinkedList<Task>();
    // List<Task> tl9 = new LinkedList<Task>();
    // List<Task> tl10 = new LinkedList<Task>();
    // List<Task> tl11 = new LinkedList<Task>();
    // List<Task> tl12 = new LinkedList<Task>();
    // List<Task> tl13 = new LinkedList<Task>();
    // List<Task> tl14 = new LinkedList<Task>();
    //
    // List<Task> tl = new LinkedList<Task>();
    //
    // tl1.add(t1);
    // tl2.add(t2);
    // tl3.add(t4);
    // tl4.add(t6);
    // tl5.add(t3);
    // tl5.add(t5);
    // tl6.add(t7);
    // tl6.add(t8);
    // tl6.add(t9);
    // tl7.add(t10);
    // tl8.add(t12);
    // tl9.add(t13);
    // tl10.add(t14);
    // tl11.add(t11);
    // tl11.add(t15);
    // tl12.add(t16);
    // tl13.add(t17);
    // tl14.add(t18);
    // tl14.add(t19);
    //
    // tl.add(t1);
    // tl.add(t2);
    // tl.add(t3);
    // tl.add(t4);
    // tl.add(t5);
    // tl.add(t6);
    // tl.add(t7);
    // tl.add(t8);
    // tl.add(t9);
    // tl.add(t10);
    // tl.add(t11);
    // tl.add(t12);
    // tl.add(t13);
    // tl.add(t14);
    // tl.add(t15);
    // tl.add(t16);
    // tl.add(t17);
    // tl.add(t18);
    // tl.add(t19);
    // tl.add(t20);
    //
    //
    // t2.setPreviousTasks(tl1);
    // t3.setPreviousTasks(tl2);
    // t4.setPreviousTasks(tl2);
    // t5.setPreviousTasks(tl3);
    // t6.setPreviousTasks(tl5);
    // t7.setPreviousTasks(tl4);
    // t8.setPreviousTasks(tl4);
    // t9.setPreviousTasks(tl4);
    // t10.setPreviousTasks(tl6);
    // t11.setPreviousTasks(tl7);
    //
    // t13.setPreviousTasks(tl8);
    // t14.setPreviousTasks(tl9);
    // t15.setPreviousTasks(tl10);
    // t16.setPreviousTasks(tl11);
    // t17.setPreviousTasks(tl12);
    // t18.setPreviousTasks(tl13);
    // t19.setPreviousTasks(tl13);
    // t20.setPreviousTasks(tl14);
    // Wbs wbs = new Wbs(tl);
    // Set<Task> task = wbs.getNoPreviousTasks();
    // for (Task task2 : task) {
    // System.out.println("taskNumber=nb="+task2.getTaskNumber());
    // }
    // Set<Task> taskt = wbs.getNoNextTasks();
    // for (Task task2 : taskt) {
    // System.out.println("taskNumber=na="+task2.getTaskNumber());
    // }
    // wbs.calculateTime();
    // wbs.calculateTimeArray();



    // long time1 = System.currentTimeMillis();
    // Task previous = new Task("1","FS",15,0);
    // List<Task> tls = new LinkedList<Task>();
    // tls.add(previous);
    // List<Task> tl = new LinkedList<Task>();
    // tl.add(previous);
    // for(int i = 2;i<=2000;i++){
    // Task tmp = new Task(String.valueOf(i),"FS",15,0);
    // tmp.setPreviousTasks(tls);
    // tls = new LinkedList<Task>();
    // tls.add(tmp);
    // tl.add(tmp);
    // }
    // long time2 = System.currentTimeMillis();
    // System.out.println("构建用时:"+(time2-time1));
    // Wbs wbs = new Wbs(tl);
    // wbs.calculateTime();
    // long time3 = System.currentTimeMillis();
    // System.out.println("计算用时:"+(time3-time2));





    //数组的计算
    long time1 = System.currentTimeMillis();
    int arrayLength = 200;
    String[] logicarray = new String[arrayLength];
    double[] delaytimearray = new double[arrayLength];
    double[] durtimearray = new double[arrayLength];

    Random random = new Random();
    for(int i = 0; i < arrayLength;i++) {
    //获得200以内的正整数为执行时间数组赋值
    durtimearray[i] =Math.abs(random.nextInt())%200;
    //获得20以内的整数为浮动时间赋值
    delaytimearray[i] =Math.abs(random.nextInt()%20);
    //获得4以内的整数为4种逻辑关系赋值
    int index = Math.abs(random.nextInt())%4;
    switch (index) {
    case 1:
    logicarray[i]="SS";
    break;
    case 2:
    logicarray[i]="FF";
    break;
    case 3:
    logicarray[i]="SF";
    break;
    default:
    logicarray[i]="FS";
    break;
    }
    }

    Task previous = new Task("task1",logicarray,delaytimearray,durtimearray);
    List<Task> tls = new LinkedList<Task>();
    tls.add(previous);
    List<Task> tl = new LinkedList<Task>();
    tl.add(previous);
    for(int i = 2;i<=5000;i++){
    String[] logicarrayi = new String[arrayLength];
    double[] delaytimearrayi = new double[arrayLength];
    double[] durtimearrayi = new double[arrayLength];
    Random randomi = new Random();

    for(int ii = 0; ii < arrayLength;ii++) {
    //获得200以内的正整数为执行时间数组赋值
    durtimearrayi[ii] =Math.abs(randomi.nextInt())%200;
    //获得20以内的整数为浮动时间赋值
    delaytimearrayi[ii] =Math.abs(randomi.nextInt()%20);
    //获得4以内的整数为4种逻辑关系赋值
    int index = Math.abs(randomi.nextInt())%4;
    switch (index) {
    case 1:
    logicarrayi[ii]="SS";
    break;
    case 2:
    logicarrayi[ii]="FF";
    break;
    case 3:
    logicarrayi[ii]="SF";
    break;
    default:
    logicarrayi[ii]="FS";
    break;
    }
    }

    Task tmp = new Task("task"+i,logicarrayi,delaytimearrayi,durtimearrayi);
    tmp.setPreviousTasks(tls);
    tls = new LinkedList<Task>();
    int previousCount = Math.abs(randomi.nextInt())%8;
    for(int ii = 0; ii < previousCount;ii++) {
    if(ii<tl.size()){
    tls.add(tl.get(ii));
    }
    }

    tl.add(tmp);
    }
    long time2 = System.currentTimeMillis();
    System.out.println("构建用时:"+(time2-time1));
    Wbs wbs = new Wbs(tl);
    wbs.calculateTimeArray();
    long time3 = System.currentTimeMillis();
    System.out.println("计算用时:"+(time3-time2));

    }
    }

    展开全文
  • 图的关键路径算法

    千次阅读 2011-11-20 21:02:18
    关键路径法(Critical Path Method, CPM)是一种基于数学计算的项目计划管理方法,是网络图计划方法的一种,属于肯定型的网络图。关键路径法将项目分解成为多个独立的活动并确定每个活动的工期,然后用逻辑关系(结束-...
     
    

    关键路径法(Critical Path Method, CPM)是一种基于数学计算的项目计划管理方法,是网络图计划方法的一种,属于肯定型的网络图。关键路径法将项目分解成为多个独立的活动并确定每个活动的工期,然后用逻辑关系(结束-开始、结束-结束、开始-开始和开始结束)将活动连接,从而能够计算项目的工期、各个活动时间特点(最早最晚时间、时差)等。

     

    头文件:CriticalPath.h

    #ifndef CRITICALPATH_H
    #define CRITICALPATH_H
    #define MAXVEX 20
    typedef int VertexType;  //图的顶点数据类型
    typedef struct edgenode{
    	int AdjVex;   //顶点的下标值
    	int weight;   //顶点的权值
    	struct edgenode* next;  //指向下一个边集点
    }EdgeNode;
    typedef struct vertexnode{
    	VertexType data; //顶点信息
    	int in; //顶点的入度
    	EdgeNode *FirstEdge;  //指向边集点
    }VertexNode;
    typedef struct graph{
    	VertexNode Vertex[MAXVEX]; //图的顶点集
    	int NumVertex,NumEdge; //图的顶点数和边数
    }Graph;
    
    void CreateGraph(Graph *G); //创建图
    void TopoLogicalSort(Graph *G); //拓扑排序算法
    void CriticalPath(Graph *G); //关键路径算法
    #endif //CRITICALPATH_H
    


    实现文件:CriticalPath.cpp

    #include "CriticalPath.h"
    #include <stdio.h>
    #include <stdlib.h>
    int *etv,*ltv; //事件最早发生时间和最迟发生时间数组
    int top2; //用于Stack2的指针
    int *Stack2; //用于存储拓扑序列的栈
    void CreateGraph(Graph *G) //创建图
    {
    	EdgeNode *e = NULL;
    	G->NumVertex = 10;
    	G->NumEdge = 13;
    	for(int i = 0;i < G->NumVertex;++i)
    	{
    		G->Vertex[i].data = i;
    		G->Vertex[i].in = 0;
    		G->Vertex[i].FirstEdge = NULL;
    	}
    	//顶点间的连接信息
    	e = (EdgeNode*)malloc(sizeof(EdgeNode)); //v0 -> v1 权值为3
    	e->next = G->Vertex[0].FirstEdge;
    	e->AdjVex = 1;
    	e->weight = 3;
    	G->Vertex[0].FirstEdge = e;
    	++G->Vertex[e->AdjVex].in;
    
    	e = (EdgeNode*)malloc(sizeof(EdgeNode)); //v0 -> v2 权值为4
    	e->next = G->Vertex[0].FirstEdge;
    	e->AdjVex = 2;
    	e->weight = 4;
    	G->Vertex[0].FirstEdge = e;
    	++G->Vertex[e->AdjVex].in;
    
    	e = (EdgeNode*)malloc(sizeof(EdgeNode)); //v1 -> v3 权值为5
    	e->next = G->Vertex[1].FirstEdge;
    	e->AdjVex = 3;
    	e->weight = 5;
    	G->Vertex[1].FirstEdge = e;
    	++G->Vertex[e->AdjVex].in;
    
    	e = (EdgeNode*)malloc(sizeof(EdgeNode)); //v1 -> v4 权值为6
    	e->next = G->Vertex[1].FirstEdge;
    	e->AdjVex = 4;
    	e->weight = 6;
    	G->Vertex[1].FirstEdge = e;
    	++G->Vertex[e->AdjVex].in;
    
    	e = (EdgeNode*)malloc(sizeof(EdgeNode)); //v2 -> v3 权值为8
    	e->next = G->Vertex[2].FirstEdge;
    	e->AdjVex = 3;
    	e->weight = 8;
    	G->Vertex[2].FirstEdge = e;
    	++G->Vertex[e->AdjVex].in;
    
    	e = (EdgeNode*)malloc(sizeof(EdgeNode)); //v2 -> v5 权值为7
    	e->next = G->Vertex[2].FirstEdge;
    	e->AdjVex = 5;
    	e->weight = 7;
    	G->Vertex[2].FirstEdge = e;
    	++G->Vertex[e->AdjVex].in;
    
    	e = (EdgeNode*)malloc(sizeof(EdgeNode)); //v3 -> v4 权值为3
    	e->next = G->Vertex[3].FirstEdge;
    	e->AdjVex = 4;
    	e->weight = 3;
    	G->Vertex[3].FirstEdge = e;
    	++G->Vertex[e->AdjVex].in;
    
    	e = (EdgeNode*)malloc(sizeof(EdgeNode)); //v4 -> v6 权值为 9
    	e->next = G->Vertex[4].FirstEdge;
    	e->AdjVex = 6;
    	e->weight = 9;
    	G->Vertex[4].FirstEdge = e;
    	++G->Vertex[e->AdjVex].in;
    
    	e = (EdgeNode*)malloc(sizeof(EdgeNode)); //v4 -> v7 权值 4
    	e->next = G->Vertex[4].FirstEdge;
    	e->AdjVex = 7;
    	e->weight = 4;
    	G->Vertex[4].FirstEdge = e;
    	++G->Vertex[e->AdjVex].in;
    
    	e = (EdgeNode*)malloc(sizeof(EdgeNode)); //v5 -> v7 权值为6
    	e->next = G->Vertex[5].FirstEdge;
    	e->AdjVex = 7;
    	e->weight = 6;
    	G->Vertex[5].FirstEdge = e;
    	++G->Vertex[e->AdjVex].in;
    
    	e = (EdgeNode*)malloc(sizeof(EdgeNode)); //v6 -> v9 权值为2
    	e->next = G->Vertex[6].FirstEdge;
    	e->AdjVex = 9;
    	e->weight = 2;
    	G->Vertex[6].FirstEdge = e;
    	++G->Vertex[e->AdjVex].in;
    
    	e = (EdgeNode*)malloc(sizeof(EdgeNode)); //v7 -> v8 权值为5
    	e->next = G->Vertex[7].FirstEdge;
    	e->AdjVex = 8;
    	e->weight = 5;
    	G->Vertex[7].FirstEdge = e;
    	++G->Vertex[e->AdjVex].in;
    
    	e = (EdgeNode*)malloc(sizeof(EdgeNode)); //v8 -> v9 权值为3
    	e->next = G->Vertex[8].FirstEdge;
    	e->AdjVex = 9;
    	e->weight = 3;
    	G->Vertex[8].FirstEdge = e;
    	++G->Vertex[e->AdjVex].in;
    }
    void TopoLogicalSort(Graph *G)
    {
    	int *Stack; //用于存储入度为0的顶点下标
    	int top = 0; //Stack栈的指针
    	int count = 0; //统计输出的顶点数
    	int gettop; //去除的顶点下标
    	Stack = (int *)malloc(sizeof(int) * G->NumVertex);
    	top2 = 0;
    	Stack2 = (int *)malloc(sizeof(int) * G->NumVertex); //存储拓扑排序的序列
    	for(int i = 0;i < G->NumVertex;++i)
    	{
    		if(!(G->Vertex[i].in)) //将入度为0的顶点存储在Stack栈中
    			Stack[++top] = i;
    	}
    	etv = (int*)malloc(sizeof(int) * G->NumVertex);
    	for(int i = 0;i < G->NumVertex;++i) //事件最早发生时间初始化为0
    	{
    		etv[i] = 0;
    	}
    	while(top != 0) //Stack栈不为空,即还有未处理完的顶点
    	{
    		gettop = Stack[top--]; //出栈
    		count++;
    		Stack2[++top2] = gettop; //将已处理的顶点压入Stack2栈中
    //		printf("V%d ",G->Vertex[gettop].data);
    		for(EdgeNode *e = G->Vertex[gettop].FirstEdge;e;e = e->next) //处理下标为gettop的顶点所连接的顶点
    		{
    			int k = e->AdjVex;
    			if(!(--G->Vertex[k].in)) //如果被指向的顶点入度减1为0的话压入Stack栈中
    				Stack[++top] = k;
    			if(etv[gettop] + e->weight > etv[k]) //事件最早发生的时间
    				etv[k] = etv[gettop] + e->weight;
    		}
    	}
    //	printf("\n");
    	if(count < G->NumVertex) //如果顶点没有完全输出
    	{
    		printf("拓扑排序错误,程序即将退出:\n");
    		system("pause");
    		exit(1);
    	}
    }
    void CriticalPath(Graph *G)
    {
    	int ete,lte; //声明事件最早发生时间和最迟发生时间的变量
    	TopoLogicalSort(G); //拓扑排序求事件的最早发生时间和拓扑序列Stack2
    	ltv = (int *)malloc(sizeof(EdgeNode) * G->NumVertex);
    	for(int i = 0;i < G->NumVertex;++i) //初始化事件最晚发生时间
    	{
    		ltv[i] = etv[G->NumVertex - 1];
    	}
    	while(top2 != 0) //如果Stack2栈不为空
    	{
    		int gettop = Stack2[top2--]; //出栈
    		for(EdgeNode *e = G->Vertex[gettop].FirstEdge;e;e = e->next) //处理下标为gettop的顶点所连接的顶点
    		{
    			int k = e->AdjVex;
    			if(ltv[k] - e->weight < ltv[gettop])
    				ltv[gettop] = ltv[k] - e->weight;
    		}
    	}
    	for(int i = 0;i < G->NumVertex;++i)
    	{
    		for(EdgeNode *e = G->Vertex[i].FirstEdge;e;e = e->next)
    		{
    			int k = e->AdjVex;
    			ete = etv[i];  //事件最早发生时间
    			lte = ltv[k] - e->weight; //事件最晚发生时间
    			if(ete == lte) //相等即在关键路径上
    			{
    				printf(" <V%d -> V%d) weight: %d\n",G->Vertex[i].data,G->Vertex[k].data,e->weight);
    			}
    		}
    	}
    }


    测试文件:main.cpp

    #include "CriticalPath.h"
    int main()
    {
    	Graph G;
    	CreateGraph(&G);
       	CriticalPath(&G);
    	return 0;
    }


     

    展开全文
  • DAG图中的关键路径算法

    千次阅读 2013-11-26 22:38:53
    简单的将就是不可以推辞的活动组成的路径,这对于工程上有着极其重要的应用,利用关键路径算法可以计算那些事件是不可推辞的,必须如期完成,下面是代码: //关键路径算法 //图的邻接矩阵表示 #include #include...

    什么是DAG图中的关键路径?简单的将就是不可以推辞的活动组成的路径,这对于工程上有着极其重要的应用,利用关键路径算法可以计算那些事件是不可推辞的,必须如期完成,下面是代码:

    //关键路径算法
    //图的邻接矩阵表示法
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <stack>
    #include <queue>
    using namespace std;
    #define Max 100
    #define Inf 0x1111
    typedef char type;
    typedef struct Grap{
    	type data[Max];
    	int value[Max][Max];
    	int n,m;
    }Grap,*pgrap;
    int Located(pgrap g,char ch){
    	for(int i=0;i<g->n;i++)
    		if(g->data[i]==ch)
    			return i;
    }
    int invalue[Max];
    int ve[Max];
    int vl[Max];
    bool trag;
    stack<int> s;
    stack<int> t;
    void Creat_grap(pgrap g){
    	printf("输入图的顶点数和边数:\n");
    	scanf("%d%d",&g->n,&g->m);
    	//printf("ksgfdkj\n");
    	getchar();
    	printf("输入图中的顶点:\n");
    	int i,j;
    	for(i=0;i<g->n;i++){
    		g->data[i]=getchar();
    		getchar();
    	}
    	for(i=0;i<g->n;i++)
    		for(j=0;j<g->n;j++)
    			g->value[i][j]=Inf;
    		printf("请输入图中的边:\n");
    		int index1,index2,value;
    		char ch1,ch2;
    		while(g->m--){
    			scanf("%c,%c,%d",&ch1,&ch2,&value);
    			getchar();
    			index1=Located(g,ch1);
    			index2=Located(g,ch2);
    			g->value[index1][index2]=value;
    			//无向图
    			//g->value[index2][index1]=value;
    		}
    }
    void In_value(pgrap g){
    	memset(invalue,0,sizeof(invalue));
    	for(int i=0;i<g->n;i++)
    		for(int j=0;j<g->n;j++)
    			if(g->value[j][i]!=Inf)
    				invalue[i]++;
    }
    void tuopu(pgrap g){
    	int i,index,count=0;
    	trag=true;
    	memset(ve,0,sizeof(ve));
    	for(i=0;i<g->n;i++)
    		if(invalue[i]==0)
    			s.push(i);
    	while(!s.empty()){
    		index=s.top();
    		s.pop();
    		t.push(index);
    		count++;
    		for(i=0;i<g->n;i++)
    			if(g->value[index][i]!=Inf){
    				if(--invalue[i]==0)
    					s.push(i);
    				if(ve[index]+g->value[index][i]>ve[i])
    					ve[i]=ve[index]+g->value[index][i];
    			}
    	}
    	if(count<g->n)
    		trag=false;
    }
    void Keyway(pgrap g){
    	if(!trag){
    		printf("图中存在环\n");
    		return ;
    	}
    	int i,j,index,end=t.top();
    	for(i=0;i<g->n;i++)
    		vl[i]=ve[end];
    	while(!t.empty()){
    		index=t.top();
    		t.pop();
    		for(i=0;i<g->n;i++)
    			if(g->value[index][i]!=Inf)
    				if(vl[i]-g->value[index][i]<vl[index])
    					vl[index]=vl[i]-g->value[index][i];
    	}
    	int early,later;
    	char tragg;
    	for(i=0;i<g->n;i++)
    		for(j=0;j<g->n;j++)
    			if(g->value[i][j]!=Inf){
    				early=ve[i];
    			    later=vl[j]-g->value[i][j];
    				tragg=(early==later)?'Y':'N';
    				printf("类型,起点,终点,最早发生时间,最晚发生时间,活动耗时\n");
    				printf("%c,%c,%c,%d,%d,%d\n",tragg,g->data[i],g->data[j],early,later,g->value[i][j]);
    			}
    }
    
    int main(){
    	Grap g;
    	pgrap p=&g;
    	Creat_grap(p);
    	In_value(p);
    	tuopu(p);
    	Keyway(p);
    	return 0;
    }
    


     

    测试数据:

    输入图的顶点数和边数:
    6 9
    输入图中的顶点:
    A
    B
    C
    D
    E
    F
    请输入图中的边:
    A,B,1
    A,C,3
    B,D,4
    B,C,1
    C,D,1
    D,E,2
    C,E,1
    E,F,1
    D,F,1
    类型,起点,终点,最早发生时间,最晚发生时间,活动耗时
    Y,A,B,0,0,1
    类型,起点,终点,最早发生时间,最晚发生时间,活动耗时
    N,A,C,0,1,3
    类型,起点,终点,最早发生时间,最晚发生时间,活动耗时
    N,B,C,1,3,1
    类型,起点,终点,最早发生时间,最晚发生时间,活动耗时
    Y,B,D,1,1,4
    类型,起点,终点,最早发生时间,最晚发生时间,活动耗时
    N,C,D,3,4,1
    类型,起点,终点,最早发生时间,最晚发生时间,活动耗时
    N,C,E,3,6,1
    类型,起点,终点,最早发生时间,最晚发生时间,活动耗时
    Y,D,E,5,5,2
    类型,起点,终点,最早发生时间,最晚发生时间,活动耗时
    N,D,F,5,7,1
    类型,起点,终点,最早发生时间,最晚发生时间,活动耗时
    Y,E,F,7,7,1


    Terminated with return code 0
    Press any key to continue ...

     


     

    展开全文
  • 基本概念:在关键路径法中,一般有以下一些时间参数:最早开始时间(Early Start)活动最早开始时间由所有前置活动中最后一个最早结束时间确定。最早结束时间(Early Finish)活动的最早结束时间由活动的最早开始...

    基本概念: 
    在关键路径法中,一般有以下一些时间参数: 

    最早开始时间(Early Start)活动最早开始时间由所有前置活动中最后一个最早结束时间确定。 

    最早结束时间(Early Finish)活动的最早结束时间由活动的最早开始时间加上其工期确定。 

    最迟结束时间(Late Finish)一个活动在不耽误整个项目的结束时间的情况下能够最迟开始的时间。它等于所有紧后工作中最早的一个最晚开始时间。 

    最迟开始时间(Late Start)一个活动在不耽误整个项目的结束时间的情况下能够最早开始的时间。它等于活动的最迟结束时间减去活动的工期。 

    总时差(Total Float) 指一项活动在不影响整体计划工期的情况下最大的浮动时间。 

    自由时差(Free Float)指活动在不影响其紧后工作的最早开始时间的情况下可以浮动的时间。 



    算法原理-前导图(PDM)法: 
    对于活动的最早开始和最早结束时间,采用正推法计算,其算法如下所示: 

    1.将第一个活动的最早开始时间设置为1. 

    2.在活动的最早开始时间上加上其工期,得到活动的最早结束时间。 

    3.根据该活动与后置活动的逻辑关系,计算后置活动应该的最早开始时间,并与其已有的最早开始时间对比,如果其后置活动还没有设置最早开始时间,则将此时间设为其最早开始时间,如果此时间早于其后置活动已有的最早开始时间,则保留后置活动的原有最早开始时间,如果此时间迟于其后置活动已有的最早开始时间,则将此时间设置为后置活动的最迟开始时间。 

    4.重复步骤2和3,直到所有活动的时间被计算完为止。 

    对于以上所示的最早时间的计算过程,可以以公式的形式表示如下: 

    当活动间的逻辑关系为SS,则计算如下 

    ESj=max{ ESi + STS} 

    当活动间的逻辑关系为FS,则计算如下 

    ESj= max{ESi+ Di+ FTS} 

    当活动间的逻辑关系为FF,计算如下 

    ESj= max{ESi+ Di - Dj +FTF} 

    当活动间的逻辑关系为SF,计算如下 

    ESj=max{ ESi - Dj +STF} 

    在计算出各个活动的最早开始和结束时间之后,就可以计算活动的自由时差,在计算前导图(PDM)的自由时差时应注意,由于引入了多种逻辑关系,并且活动间可以存在延时,所以其计算方法与箭线图(ADM)的计算方法不一样。 

    对于前导图(PDM)的活动间,除了延时还可以存在时间间隔(LAG),一般可以按照下面的方式计算。 

    当活动间的逻辑关系为SS,则计算如下 

    LAGi-j= ESj- ESi- STS 

    当活动间的逻辑关系为FS,则计算如下 

    LAGi-j= ESj- EFi- FTS 

    当活动间的逻辑关系为FF,计算如下 

    LAGi-j= EFj- EFi- FTF 

    当活动间的逻辑关系为SF,计算如下 

    LAGi-j= EFj- ESi- STF 

    则对于任意一个活动,其自由时差为 

    FFi=min{ LAGi-j} 

    最后一个活动的自由时差为0. 

    对于总时差,终点节点的总时差为0,对于其它任意一个节点,总时差按照下式进行计算 

    TFi=min{TFj+ LAGi-j} 

    对于任意一个活动的最晚开始时间可以由其最早开始时间加上总时差得到,同样,其最晚开始时间可以由最早结束时间加上其总时差得到,公式表示如下 

    LSi=ESi+TFi 

    LFi=EFi+TFi 

    代码分析:

    首先根据如上概念,抽象出一些属性:

       private String taskNumber;//任务编号   
       private String logic;//任务之间的逻辑关系   
          
       private double earlyStartTime;//最早开始时间   
       private double earlyFinishTime;//最早结束时间   
       private double lateStartTime;//最晚开始时间   
       private double lateFinishTime;//最晚结束时间   
       private double dut;//执行时间   
       private double delayTime;//延迟时间   
       private double slack;//机动时间   

    创建一个构造器

        /*  
         * taskNumber 任务编号  
         * logic 与前置任务的逻辑关系  
         * dut 任务执行时间  
         *delayTime 提前滞后时间  
         */  
        public Task(String taskNumber,String logic, double dut, double delayTime) {   
            super();   
            this.taskNumber = taskNumber;   
            this.logic = logic;   
            this.dut = dut;   
            this.delayTime = delayTime;   
        }   

    然后是定义最早开始时间和最早结束时间,最晚开始时间和最晚结束时间的方法。

    再通过一个计算类验证其正确性。

    相关资料

    转载于:https://www.cnblogs.com/larryzhang/archive/2012/06/20/2556228.html

    展开全文
  • Floyd算法又称为插点,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径算法。 Floyd算法能够处理带负权重的边的有向图但不能包含负权重环。 算法思想: 从起始顶点开始,依次加入一个顶点,...
  • 举个例子,我们学数学的时候,一定是先学习加减法,然后学乘除,接着学习平方、根号等。不可能反着学。这就是拓扑排序。 拓扑排序可能是不唯一的,例如学完加减法之后,可以先学乘法,也可以先学除。 拓扑排序不...
  • 关键路径

    2020-03-09 17:26:18
    关键路径的求一般是针对有向无环图的,常用来解决工程中的问题,前面我们学过Bellman和SPFA算法,如果我们给每条边变成相反数就可以求解关键路径了,当然关键路径不止一种求,数据结构中给出的关键路径的...
  • 最小生成树 定义:在一个联通网的所有生成树中,各边的代价之和最小的那棵生成树称为该连通图的的最小生成树...加点 假设N=(V,E)时连通图,TE是N上最小生成树中边的集合。 1、U={uo}(uo∈V),TE={}. 2、在所有u∈U,v∈
  • 关键路径法将项目分解成为多个独立的活动并确定每个活动的工期,然后用逻辑关系(结束-开始、结束-结束、开始-开始和开始结束)将活动连接,从而能够计算项目的工期、各个活动时间特点(最早最晚时间、时差)等。...
  • 首先贴一下百度百科对CPM的定义:关键路径法(Critical Path Method, CPM)是一种基于数学计算的项目计划管理方法,是网络图计划方法的一种,属于肯定型的网络图。关键路径法将项目分解成为多个独立的活动并确定每个...
  • :公交乘客出行路径选择是公交乘客信息系统的关键技术,提出以换乘次数最少为首要目标、出行距离 最短为第二目标的算法,本算法是基于广度优先搜索并结合蚂蚁算法提出公交路线最短路径选择的新算法 关键词:最短路径...
  • 实验七 图的深度优先遍历(选做,验证性实验,4学时) 实验目的 熟悉图的数组表示和邻接表存储结构,掌握构造有向图、无向图的算法 ,在掌握以上知识的基础上,...(4)在邻接表上实现拓扑排序、关键路径的求...
  • 对Dijkstra算法改进,并求解关键节点(起点,终点和必经节点)间的最短路径,进而从关键节点所构成的矩阵中采用回溯得到目标路径。通过实际的算法实现,测试大量的有向非负权图数据,证实了算法的有效性和正确性。
  • 关键活动算法

    2020-12-18 21:27:10
    关键路径 在AOE网中,一个顶点表示一个工程事件,而一条边表示一个活动。 关键活动 简单理解:当该弧的最早发生时间与最晚发生时间相同时,改活动(即为弧)即为关键活动。 算法实现(伪代码) 关于具体算法中用...
  • 在学习数据结构部分时对图的应用(最短路径和关键路径)特别困惑,所以总结了笔记,并分享出来,特别是蓝色和红色字体。有问题请及时联系博主:Alliswell_WP,转载请注明出处。 重点难点:图的应用(最短路径和关键...
  • 普利姆算法和克鲁斯卡尔算法是两个利用MST性质构造最小生成树的算法。 一、普利姆算法(“加点”) 二、克鲁斯卡尔算法
  • 路径规划是移动机器人关键技术,针对移动机器人在已知环境下避障和搜索最优路径问题,提出了一种运用栅格法辅以遗传算法进行搜索的方案。其中栅格用来划分地图,而后为机器人自身周围八个方位进行二进制编码,这些方位...
  • 前面我们已经了解到了无环有向图怎样求关键路径的方法,今天我们来看看无向图怎样求最短路径,这在实际应用过程中的作用很大,不如交通路线图,从出发点到终点,走哪条路用时最短,或者花费最少等问题。 我们先来看...
  • 车辆路径问题(VRP) 是物流研究领域中一... 指出可行解问题是蚁群算法关键问题, 并重点对该问题进行了研究, 提出了近似解可行化等解决策略. 实验结 果表明, 自适应蚁群算法性能优良, 能够有效地求解VRP 问题.</p>
  • 第三部分首先回顾了物流配送中现有的算法,然后作者把动态规划的思想运用到车辆路径问题中,以动态规划为理论,并做了改进用以解决物流配送最短路径问题;第四部分结合《电子商务与现代物流系统集成平台技术研究开发》...
  • 栅格选的大,环境分辨率较小,环境信息存储量小,决策速度快,但在密集障碍物环境中发现路径的能力较弱。 2.障碍物栅格确定 当机器人新进入一个环境时,它是不知道室内障碍物信息的,这就需要机器人能够遍历整个...
  • 1.实验目的 熟悉图的数组表示和邻接表存储结构,掌握构造有向图和无向图的算法,在掌握以上知识的基础上,熟悉图...(4)在邻接表上实现拓扑排序、关键路径的求,在邻接矩阵上实现最短路径,最小生成树的求 ...
  • 关键路径问题就是求一个带权的无环图中两节点间的最长路径问题。
  • Ford-Fulkerson算法 ... 该算法关键是找到s到t的增广路,这可通过标号实现,具体规则为: · 一个节点先进行标号,再检查。一个节点可处于三个状态之一:已标号并且已检查;已标号但未检查;未标
  • 局部搜索算法是对一个或多个状态进行评价和修改,而不是系统地从初始状态开始的路径。这些算法适用于关注那些关注解状态而不是路径代价的问题。局部搜索算法从单个当前节点出发,通常只移动到它的临近状态,一般保存...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 306
精华内容 122
关键字:

关键路径法算法