Change Dir

先知cd——热爱生活是一切艺术的开始

统计

留言簿(18)

积分与排名

“牛”们的博客

各个公司技术

我的链接

淘宝技术

阅读排行榜

评论排行榜

深入理解动态规划的一系列问题(13)

今天介绍的这个问题还是一个任务调度的问题(Flowshop问题),每个过程i有两个任务A和B,其中有个约束,那就是A一定要在B之前完成,任务A和B分别由两个处理器完成,编号为1和2,每个过程i有对应自己任务的完成时间,选择如何调度这些过程,会产生不同的任务总体完成时间,问题的目标就是要找到最佳完成时间的策略。举例来讲,有4个过程为{0,1,2,3},每个过程对应的A任务完成时间为{3,4,8,10},B任务完成时间为{6,2,9,15},如果处理器按照这个顺序去处理任务,依据约束条件,完成过程如下表表示:

image 可以看出这个方案的调度时长需要40。

如果用DP去求解这个问题,首先定义状态,我们定义过程d的A任务完成时间为pd,B任务完成时间为qd,那么引入一个虚拟阶段号k,k表示上一次被确认调度的A和B任务各自完成中间那段流失的时间(可能不是很好理解,这里解释一下,为什么取这个值作为状态,首先对于pd和qd这都是固定计算成本,那么导致任务不能连续运转的原因就是有A在B前完成这个约束,对于上面的例子,我们看到B3任务并不能在B2任务结束后马上开始,而一定要等到A3任务结束才可以,B2结束后到A3结束前这段时间即15-11这4个时间单位的时间就是这里的k了,定义了这个k后,我们就可以知道目标状态是要使k=0且未被调度的任务集合),定义S为剩余的过程集合,所以状态为(k,S),这个状态对于一个过程的A和B任务如果没有延迟(k<pd),那么k=qd,反之有延迟则延迟时间为max(k-pd,0),所以一个调度过程d开始后的时间成本会记为A任务时间pd+延迟时间max(k-pd,0)+B任务时间qd。所以DPFE即f(k,S)=min d∈S{pd+f(max(k-pd)+qd,S-{d})}。初始状态对于S是空集,那么f(k,S)=k。于是对于上面的具体问题,方程求解最优时间是38,决策序列为d1=0,d2=2,d3=3,d4=1。

过程源码如下:

   1: /*
   2:  * Copyright (C) 2013 changedi
   3:  *
   4:  * Licensed under the Apache License, Version 2.0 (the "License");
   5:  * you may not use this file except in compliance with the License.
   6:  * You may obtain a copy of the License at
   7:  *
   8:  * http://www.apache.org/licenses/LICENSE-2.0
   9:  *
  10:  * Unless required by applicable law or agreed to in writing, software
  11:  * distributed under the License is distributed on an "AS IS" BASIS,
  12:  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13:  * See the License for the specific language governing permissions and
  14:  * limitations under the License.
  15:  */
  16: package com.jybat.dp;
  17:  
  18: import java.util.HashSet;
  19: import java.util.Set;
  20:  
  21: //Flowshop Problem
  22: public class FLOWSHOP {
  23:  
  24:     private static int[] first = { 3, 4, 8, 10 }; // sum=25
  25:     private static int[] second = { 6, 2, 9, 15 }; // sum=32
  26:     // upper bound on final completion time is 25+32:
  27:     private static int sum = 57;
  28:     private static int m = first.length;
  29:  
  30:     private static Set<Integer> setOfAllItems = new HashSet<Integer>();
  31:     
  32:     static{
  33:         setOfAllItems.add(0);
  34:         setOfAllItems.add(1);
  35:         setOfAllItems.add(2);
  36:         setOfAllItems.add(3);
  37:     }
  38:     
  39:     private static int fct(int t, int d) {
  40:         return Math.max(t - first[d], 0) + second[d];
  41:     }
  42:     
  43:     public static double f(Set<Integer> set, int t){
  44:         if(set.isEmpty())
  45:             return t;
  46:         double min = Double.MAX_VALUE;
  47:         for(int d : set){
  48:             Set<Integer> tmpSet = copySet(set);
  49:             tmpSet.remove(d);
  50:             double tmp = first[d]+f(tmpSet,fct(t,d));
  51:             if(tmp<min){
  52:                 min=tmp;
  53:             }
  54:         }
  55:         return min;
  56:     }
  57:  
  58:     private static Set<Integer> copySet(Set<Integer> set) {
  59:         Set<Integer> s = new HashSet<Integer>();
  60:         for(int x : set){
  61:             s.add(x);
  62:         }
  63:         return s;
  64:     }
  65:  
  66:     /**
  67:      * @param args
  68:      */
  69:     public static void main(String[] args) {
  70:         System.out.println(f(setOfAllItems,0));
  71:     }
  72:  
  73: }


posted on 2014-06-03 19:24 changedi 阅读(1368) 评论(0)  编辑  收藏 所属分类: 算法


只有注册用户登录后才能发表评论。


网站导航: