精华内容
下载资源
问答
  • 最优批处理问题

    2020-04-19 19:12:11
    最优批处理问题 1.问题描述:在一台超级计算机上,编号为1,2……n的n个作业等待批处理。批处理的任务就是将这n个作业分成若干批,每批包含相邻的若干作业。从时刻0开始,分批加工这些作业。在每批作业开始前,机器...

    最优批处理问题

    1.问题描述:在一台超级计算机上,编号为1,2……n的n个作业等待批处理。批处理的任务就是将这n个作业分成若干批,每批包含相邻的若干作业。从时刻0开始,分批加工这些作业。在每批作业开始前,机器需要启动时间s,而完成这批作业所需的时间是单独完成批中各个作业需要时间的总和。单独完成第i个作业所需的时间是ti,所需的费用是它的完成时刻乘以一一个费用系数fi。同一批作业将在同一时刻完成。

    例如,如果在时刻T开始一批作业x,x+1,,x+k,则这一~批作业的完成时刻均为T+S+(tx, +tx+1 +...+tx+k)。最优批处理问题就是要确定总费用最小的批处理方案。

    例如,假定有5个作业等待批处理,且S = 1,(t,t2,ts,t4,t)=(1,3,4,2,1),(f1,f2,f3,f4,f5)=(3,2,3,3,4)如果采用批处理方案{1,2},{3},{4,5},则各作业的完成时间分别为(5,5,10,14,14),各作业的费用分别为(15,10,30,42,56),因此,这个批处理方案总费用是153。
    算法设计:对于给定的待批处理的n个作业,计算其总费用最小的批处理方案。
     

    2.最优子结构:

    完成n份作业的最优调度已经确定为S批次,第一批次有k份作业,后S-1批次的方案就是后n-k份作业的最优调度。

    3.状态转移方程

    C(begin,i) 是在开始时间为begin时,完成i~n号作业的最小费用,k是它的最优调度中第一批次的编号最大的作业:

    第一批次作业处理完的时间为:Ti=(begin+S+∑ti)

    C(begin,i)=min{ Ti*(∑fi) +C( Ti ,k+1)}     i=<k<=n

    (开始时间+开机时间+第一批次作业总共时间)*∑第一批次作业的费用系数 +k+1~n份作业的最小开销

    4.代码:

    int MinCost(int S,int n,int t[],int f[]){
    	int i,j,k,maxt=0,cost,ff,tt;
    	for(i=0;i<n;i++){
    		maxt+=t[i];
    	}
    	maxt+=n*S;
    	int C[n+1][maxt+1];
    	for(i=n;i>0;i--){ 
    		for(j=maxt;j>=0;j--){ 
    			C[i][j]=MaxInt;
    		}
    	} 
    
    	for(i=n;i>0;i--){//i~n个物品 
    		for(j=maxt;j>=0;j--){//j时刻开始 
    			ff=0;tt=S+j;
    			for(k=i;k<=n;k++){//[i,k] 
    				ff+=f[k-1];tt+=t[k-1];
    				cost=ff*tt;
    				if(k!=n) cost+=C[k+1][tt];//如果没有完成全部的作业,其后还有作业 k+1~n 
    				if(cost<C[i][j])
    				      C[i][j]=cost
    			}
    		}
    	} 
    			
    	return C[1][0];
    }

     

    展开全文
  • 问题描述: 在一台超级计算机上,编号为1,2,…,n的n个作业等待批处理。批处理的任务就是将这n个作业分成若干批,每批包含相邻的若干作业。从时刻0开始,分批加工这些作业。在每批作业开始前,机器需要...最优批处理

    问题描述:
    在一台超级计算机上,编号为1,2,…,n的n个作业等待批处理。批处理的任务就是将这n个作业分成若干批,每批包含相邻的若干作业。从时刻0开始,分批加工这些作业。在每批作业开始前,机器需要启动时间S,而完成这批作业所需的时间是单独完成批中各个作业需要时间的总和。单独完成第i个作业所需的时间是ti,所需的费用是它的完成时刻乘以一个费用系数fi。同一批作业将在同一时刻完成。例如,如果在时刻T开始一批作业x,x+1,…,x+k,则这一批作业的完成时刻均为T+S+(tx+tx+1+…+tx+k)。最优批处理问题就是要确定总费用最小的批处理方案。例如,假定有5个作业等待批处理,且S=1,(t1,t2,t3,t4,t5)=(1,3,4,2,1),(f1,f2,f3,f4,f5)=(3,2,3,3,4)。如果采用批处理方案{1,2},{3},{4,5},则各作业的完成时间分别为(5,5,10,14,14),各作业的费用分别为(15,10,30,42,56),因此,这个批处理方案总费用是153。
    算法设计
    对于给定的待批处理的n个作业,计算其总费用最小的批处理方案。
    数据输入
    由文件Input.txt提供输入数据。文件的第1行是待批处理的作业数n,第2行是启动时间S。接下来每行有2个数,分别为单独完成第i个作业所需的时间是ti和所需的费用系数fi。
    结果输出
    将计算出的最小费用输出到文件output.txt中。

    输入文件示例
    Input.txt output.txt
    5 153
    1
    1 3
    3 2
    4 3
    2 3
    1 4

    设计思路:
    分析题目,因为每批完成的作业必须相邻,即只能{1,2}{3},不能{1,3}{2},因此可以用动态规划来解决。设置一个minBatchCost数组,minBatchCost[i][t]表示处理第i到第n-1个作业,从时间t开始的最小开销。调用minBatchCost[0][0],即为处理第0个作业到第n-1个作业,从0时刻开始的最小开销,即为题目所求。
    对于待处理作业i到n-1,不断求出第i到i+1,i到i+2……i到n-1的最小花费并填入minBatchCost。只要没有计算到第n-1个作业,就递归处理后面的任务,直到处理完所有的作业。

    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<string.h>
    #include<limits.h>
    #define MAXN 20
    #define MAXT 20
    
    //定义全局变量:作业总数n,启动时间S,每个作业花费时间的数组times,
    //费用系数costs,minBatchCost[i][t]表示从t时刻开始处理第i到第n个作业总花费
    int n = 0;
    int S = 0;
    int times[MAXN];
    int costs[MAXN];
    int minBatchCost[MAXN][MAXT];
    //prefixTime[i]表示处理前i个作业花费的总时间,Cost类似
    int prefixTime[MAXN];
    int prefixCost[MAXN];
    
    //读取文件中的作业处理时间和作业完成费用并记录入time[]和fare[]
    void readTimeAndCost ()
    {
    	FILE*f = fopen ( "D:\\学习\\大三上\\算法设计与分析\\实验四报告+附件\\input(2).TXT" , "r" );
    	if (f == NULL)
    	{
    		printf ( "读取文件错误" );
    		return;
    	}
    	fscanf ( f , "%d" , &n );
    	fscanf ( f , "%d" , &S );
    	for (int i = 0; i < n; i++)
    	{
    		fscanf ( f , "%d" , &times[i] );
    		fscanf ( f , "%d" , &costs[i] );
    	}
    }
    
    //初始化minBatchCost和prefixTime,prefixCost
    void initData ()
    {
    	memset ( minBatchCost , -1 , sizeof ( minBatchCost ) );
    
    	for (int i = 0; i < n; i++)
    	{
    		prefixTime[i] = times[i];
    		prefixCost[i] = costs[i];
    		if (i != 0)
    		{
    			prefixTime[i] = prefixTime[i - 1] + times[i];
    			prefixCost[i] = prefixCost[i - 1] + costs[i];
    		}
    	}
    }
    
    //求处理第x到第y个任务的总时间和费用系数,最容易想到的当然是直接for循环times[x]+…+times[y],
    //不过这样的话会有很多不需要的重复计算,因此我们另外定义一个prefixTime和prefixCost数组来计算
    //求某次批处理第x到第y个作业花费的总时间
    int getBatchTimes (int x,int y)
    {
    	return prefixTime[y] - prefixTime[x] + times[x];
    }
    
    //求某次批处理第x到第y个作业花费的总费用系数
    int getBatchCosts ( int x , int y )
    {
    	return prefixCost[y] - prefixCost[x] + costs[x];
    }
    
    //求最优批处理方案
    int optimalBatch ( int x , int t )
    {
    	//动态规划的保存了已经计算过的部分,因此我们先判断是否已经求出minBatchCost[x][t]
    	if (minBatchCost[x][t] == -1)
    	{
    		int minCost = INT_MAX;
    		//处理第x到第y个作业
    		for (int y = x; y < n; y++)
    		{
    			int batchCosts = getBatchCosts ( x , y );
    			int endBatchTime = t + S + getBatchTimes ( x , y );
    			int totalCosts = batchCosts * endBatchTime;
    			//如果y+1<n,说明作业还没处理完,则剩余任务递归调用函数求出剩余任务的最小花费加上前面的花费即为总花费
    			if (y + 1 < n)
    			{
    				totalCosts += optimalBatch ( y + 1 , endBatchTime );
    			}
    			minCost = ( minCost < totalCosts ? minCost : totalCosts );
    		}
    		minBatchCost[x][t] = minCost;
    	}
    	return minBatchCost[x][t];
    }
    
    int main ()
    {
    	readTimeAndCost ();
    	initData ();
    	int cost = optimalBatch ( 0 , 0 );
    	printf ( "总费用最小的批处理方案的总费用为:%d\n" , cost );
    
    	//写入文件函数较简单不单独写一个函数
    	FILE* f = fopen ( "D:\\学习\\大三上\\算法设计与分析\\实验四报告+附件\\output(2).TXT" , "w" );
    	fprintf ( f , "%d" , cost );
    	fclose ( f );
    }
    
    

    实验结果:
    在这里插入图片描述

    展开全文
  • 这道题也可以运用动态规划的算法解决,乍一看好像看不出来有什么最优子结构的性质,这道题目我们不能把它看作是最长升序子序列那样,一个一个元素拿出来分解成若干个含有重复的子问题,这种拆分的办法这个问题不适用...

    题目介绍

    题目摘选自《计算机算法设计与分析(第5版)》,作者是王晓东,题目如下
    在这里插入图片描述

    分析

    这道题也可以运用动态规划的算法解决,乍一看好像看不出来有什么最优子结构的性质,这道题目我们不能把它看作是最长升序子序列那样,一个一个元素拿出来分解成若干个含有重复的子问题,这种拆分的办法这个问题不适用。

    这道题我们需要以分组为单位进行拆分,比如说题目给的例子{1,2}{3}{4,5},这是原问题的最优解,我们把第一组拆分出来,那么剩下的{3}{4,5}这两组实际上就是子问题1:3,4,5这三个作业中的最优解,而如果我们只是单纯的把1拿出来,那么剩下的{2}{3}{4,5}可不一定就是子问题2:2,3,4,5中的最优解了。我们弄清楚这个问题之后,就可以仔细分析,写出状态转移方程了。

    假如说我们以作业2为例,前面的子问题1的最优解为{3}{4,5},假设这个子结构的花销为dp[2](数组从0开始),那么我们有很多种选择方法,比如{2}{3}{4,5},那么这个对应的值就是dp[2],也就是2本身一组的自己开销,加上{3}{4,5}的花销(注意这里的花销是{3}{4,5}在第二个作业处理的时间内造成的花销,因为题目要求,第二个作业处理结束之后的时间内的开销就是dp[2])。

    再举一个例子,比如我们选择{2,3}{4,5}的分组方式,也就是我们选择的切分点在第三个元素,那么就是dp[3](注意这里是第四个元素的dp值),也就对应了{4,5}在{2,3}组处理之后的时间段内造成的开销,我们还要加上数组{2,3}和数组{4,5}在处理{2,3}这段时间内造成的开销。

    对于所有的切分方式,我们都要进行计算,要找到一个造成最终的开销最小的点,这个点就是子问题的答案。

    所以状态转移方程为:
    dp[i] = min(dp[i],dp[j]+(S+ti+ti+1+…+tj-1)*(fi+fi=1+…+fn-1))
    后面的开销之所以要把从i往后的开销都要算上的原因在上面已经具体说明。

    代码

    //program:Optimal batch problem
    //author:William.L
    //version:v 1.0
    
    #include <iostream>
    #include <fstream>
    #define MAXN 1000000000
    using namespace std;
    int my_min(int a,int b){
        return (a < b) ? a : b;
    }
    
    int my_accumulate(int* src,int str,int ends){
        if (str > ends){
            return -1;
        }
        int sum = 0;
        for (int i = str;i <= ends; i++){
            sum += src[i];
        }
        return sum;
    }
    
    int main(){
        int num;//works number.
        ifstream in("test file.txt");
        int S;//the machine's start time.
        in >> num >> S;
        int t[num+1],f[num+1];//t means time , f means cost per time.
        for (int i = 0;i < num; i++){
            in >> t[i] >> f[i];
        }
        t[num] = f[num] = 0;//add one after the last work to calculate.
        in.close();
        int dp[num+1];//the array dp[i] means the lowest cost of the array start with the i'th work.
        for (int i = 0;i < num; i++){
            dp[i] = MAXN;
        }
        dp[num] = 0;//the the after the last is 0
        for (int i = num-1; i >= 0; i--){
            for(int j = i + 1; j <= num; j++){
                dp[i] = my_min(dp[i],dp[j]+ ((S + my_accumulate(t,i,j-1)) * my_accumulate(f,i,num-1) ) );
                //This is the most important step, find the good position to cut the array(point j)
                //the number after j use the best answer of from j to n-1
                //the number before j, put the works from i to j-1 together.
            }
        }
        ofstream out("test file.txt",ios::app);
        out << dp[0] << endl;
        out.close();
        return 0;
    }
    
    
    展开全文
  • 问题描述 在一台超级计算机上,编号为1,2,3···的n个作业等待批处理批处理的任务就是将这n个作业分成若干批,每批包含相邻的若干作业。从时刻0开始,分批加工这些作业。在每批作业开始前,机器需要启动时间S,而...

    问题描述

    在一台超级计算机上,编号为1,2,3···的n个作业等待批处理。批处理的任务就是将这n个作业分成若干批,每批包含相邻的若干作业。从时刻0开始,分批加工这些作业。在每批作业开始前,机器需要启动时间S,而完成这批作业所需的时间是单独完成批中各个作业需要时间的总和。单独完成第i个作业所需的时间是 ti,所需的费用是它的完成时刻乘以一个费用系数fi。同一批作业将在同一时刻完成。例如,如果在时刻 T 开始一批作业 x,x+1,x+2···x+k, 则这一批作业的完成时刻均为T+S+(tx+tx+1tx+2···+tk)。最优批处理问题就是要确定总费用最小的批处理方案。
    例如,假定有5个作业等待批处理,且S=1,(t1,t2,t3,t4,t5)=(1,3,4,2,1),(f1,f2,f3,f4,f5)=(3,2,3,3,4)如果采用批处理方案(1,2),(3),(4,5),则各作业的完成时间分别为(5,5,10,14,14),各作业的费用分别为(15,10,30,42,56),因此这个批处理方案总费用是153
    算法设计:
    对于给定的待批处理的个作业,计算其总费用最小的批处理方案。
    样例输入
    5
    1
    1 3
    3 2
    4 3
    2 3
    1 4
    样例输出
    153
    **

    分析

    设m[i][begin]表示从时间begin开始,处理第i~n个作业的最小总费用
    例如对于1-5作业来说,m[3][5]就表示在时刻5时候,开始执行3~5的作业
    而3~5可以有多种批处理手法,比如:{3}{4}{5}、{3}{4,5}、{3,4}{5}、{3,4}{5}
    因此需要将这些情况都计算出来,取最小值
    假设用j将3~5分为两部分,有两种分法:
    1.j = 4,则将3~5分为{3}{4,5}两部分
    2.j = 5,则将3~5分为{3,4}{5}两部分
    设前一部分为第一批作业,后一部分则为第二批作业
    先执行第一批作业
    j = 4时,开始时间为begin,
    结束时间为 Ti = begin+s+t3, Fi = f3, price1 = Ti * Fi + m[4][Ti];
    m[4][Ti]就是 递归计算{4,5}的最小费用
    j = 5时,开始时间为begin,
    结束时间为 Ti = begin+s+t3+t4, Fi = f5, price2 = Ti * Fi + m[5][Ti];
    通过上面的例子,可以得出以下状态转移方程

    m[i][begin] = min{ Ti * Fi + m[j][Ti] }   (i<j<=n+1)
      Ti = begin + s + ti + t(i+1) + t(i+2) + ... + t(j-1);
      Fi = fi + f(i+1) + ... + f(j-1);

    代码

    #include<stdio.h>
    void solve(int n,int s,int T[],int F[]){
     //计算总的时间,最优批处理的时间肯定不会超过这个总时间 
     int sum_time = 0;
     for(int i = 1; i <= n; i++) sum_time += T[i];
     sum_time += n*s;
     //初始化m状态数组 
     int m[n+1][sum_time+1];
     for(int i = 1; i <= n; i++){
      for(int begin = sum_time; begin >= 0; begin--)
       m[i][begin] = 99999;
     }
     
     for(int i = n; i > 0; i--){//从第n个作业开始倒序计算 
      for(int begin = sum_time; begin >= 0; begin--){//开始时间从最大的开始 
       
       int Ti = begin + s;//开始执行的时间 
       int Fi = 0;
       
       for(int j = i+1; j <= n+1; j++){//分别从j = i+1处到j = n处把[i:n]分为[i:j-1]和[j:n] 
        Fi += F[j-1];
        Ti += T[j-1];
        int price = Ti * Fi;
        if(j != n+1) price += m[j][Ti];//如果j = n+1,也就是说单独处理第i=n个作业,直接用Ti*Fi就好了,因为后面没有其他作业了 
        if(price < m[i][begin])//找出m[i][begin]的最小值 
         m[i][begin] = price;
       }
      }
     }
     printf("最小总费用为:%d",m[1][0]);
    }
    int main(){
     int n,s;
     scanf("%d",&n);
     scanf("%d",&s);
     int t[n+1],f[n+1];
     for(int i = 1; i <= n; i++){
      scanf("%d %d",&t[i],&f[i]);
     }
     solve(n,s,t,f);
     return 0;
    }

    运行结果

    展开全文
  • C++动态规划算法之最优批处理问题

    千次阅读 2020-04-16 23:38:09
    问题描述 在一台超级计算机上,编号为1,2,3···的n个作业等待批处理批处理的任务就是将这n个作业分成若干批,每批包含相邻的若干作业。从时刻0开始,分批加工这些作业。在每批作业开始前,机器需要启动时间S,而...
  • 问题描述: 在一台超级计算机上,编号为1,2, ,  n 的 n 个作业等待批处理批处理的任务就是将 这 n 个作业分成若干批,每批包含相邻的若干作业。从时刻 0 开始,分批加工这些作业。在 每批作业开始前,机器需要...
  • 一、实验内容及要求1....3.求出最优批处理作业调度总时间及作业安排顺序。二、实验步骤1、手工输入任务执行时间数组;2、输出作业总时间和作业的安排顺序。 package saunfafenxi; import java.util....
  • import math m = [[2,3,2],[1,1,3]] # ...def Flow(m): # 初始化调度问题 n = len(m[0]) X = [i for i in range(n)] t1 = 0 # 第一个机器的当前作业完成时间点 t2 = 0 # 第二个机器的当前作业完成时间点 Backtrace
  • 批处理作业问题

    2016-12-24 12:13:36
    #include //参照课本程序 #define n 3 int M[n][2] = { 2, 1, 3, 1, ... //当前最优作业调度 int f2[n]; // 机器2完成处理时间 int f1; //机器1完成处理时间 int f; //完成时间和 int bestF; //
  • 摘要摘要:对车间作业调度问题特征与最优完工时间之间的关系进行了统计研究。为此,手动构造了JSSP的380个新颖的特征,每一个都代表一个特定的问题特征,然后我们借助机器学习中常用的统计分析度量,如皮尔逊相关系数...
  • 然后, 分析多级批处理调度问题最优性质, 提出分批优化规则和自组织选择策略, 并在此基础上给出自组织优化调度算法; 最后, 通过调度实例求解结果表明, 所提方法能在短时间内获得问题的最优解或近优解, 进而验证了...
  • PreparedStament是大家在做单个数据库查询和更新中经常用到的一个API,也经常用来做一些批处理的插入操作,但对这个接口是如何运行和性能怎样才能达到最优方面了解较少。下面我们用例子和数据来说明这两个问题。 ....
  • 项目转战微端后,遇到一个问题:贴图如果不是pot(power of two),无法压缩成最优格式dxt,最明显的区别是,内存占用过大。差距,举例,如图: 是不是很夸张?然后看了下texture 的import settings,发现pot其实是...
  • 问题描述: 在一台超级计算机上,编号为1,2,…,n的n个作业等待批处理批处理的任务就是将这n个作业分成若干批,每批包含相邻的若干作业。从时刻0开始,分批加工这些作业。在每批作业开始前,机器需要启动时间S,...
  • publicclassBatch{//回溯法处理批处理作业调度问题staticintn;//作业数int[]Order;//作业顺序int[]bestOrder;//最优的作业顺序staticintbestf=Integer.MAX_VALUE;;//...import java.io.*;public class Batch { //...
  • 批处理作业调度问题要求确定这n个作业的最优处理顺序,使得从第一个作业再机器1上处理开始,到最后一个作业再机器3上处理结束所需的时间最少。 例: 作业-机器矩阵为 问题示例: 这些任务的一个执行序列为: 1....
  • =n),批处理作业调度问题要求确定这n个作业的最优处理顺序,使得从第1个作业在机器1上处理开始,到最后一个作业在机器2上处理结束所需时间最少。 例:作业-机器时间关系表为 约束条件: 当前作业的执行时间和必须...
  • 解决was启动缓慢 超时问题

    千次阅读 2015-08-13 10:13:00
    有个网站项目运行时间很久了,上传的文件和生成的静态页面越来越多,最近修改某些功能后,启动...2:通过写批处理命令代替手动剪切的操作。但这些都不是最优解决方案,后来网络组一位大牛周同学,建议使用windows提供的
  • 算法设计作业总结

    2019-03-07 17:40:15
    1.作业调度问题 动态规划的流水作业调度或回溯法的批处理作业调度(待定) 2.动态规划的矩阵连乘问题 3.回溯法求解0-1背包问题 4.分支限界法求解0-1背包问题 5.分支限界法求解旅行售货员问题 作业...
  • 算法设计与分析王晓东

    热门讨论 2011-08-30 09:58:18
    书名:算法设计与分析 作者:王晓东 图书目录 第1章 算法引论 1.1 算法与程序 1.2 表达算法的抽象机制 1.3 描述算法 1.4 算法复杂性分析 ...2.10 最接近点对问题 ...3.1 矩阵连乘问题 ...8.4.6 哈密顿回路问题
  • 在这种情况下调度不是最优的解决方案,主要问题是如何在任意时间使用依赖于调度程序的DataPipeline调度数据处理过程。这里有一个解决方案。首先,创建一个简单的管道,使用来自AmazonS3的数据对
  • Lecture 7 最优间隔分类器问题 Topics: Optimal Margin Classifier, Lagrange Duality, Karush-Kuhn-Tucker (KKT) Conditions, SVM Dual, The Concept of Kernels 主题:最优间隔分类,拉格朗日对偶,KKT条件,SVM...
  • 1 批处理系统  1. 2. 2 多道程序系统  1. 2. 3 分时系统  1. 3 桌面系统  1. 4 多处理器系统  1. 5 分布式系统  1. 5. 1 客户机一服务器系统  1. 5. 2 对等系统  1. 6 集群系统  1. 7 实时系统  1. 8 ...

空空如也

空空如也

1 2
收藏数 33
精华内容 13
关键字:

最优批处理问题