精华内容
下载资源
问答
  • 机器调度问题

    2021-01-13 15:59:39
    有m台机器处理n个作业,设作业i的处理时间为ti,则对n个作业进行机器分配,设计算法进行合理调度,使得m台机器上处理n个作业所需要的总时间最短。 (1)为给出的作业根据时间数分配机器。将作业按其所需时间的递减...

    需求分析

    有m台机器处理n个作业,设作业i的处理时间为ti,则对n个作业进行机器分配,设计算法进行合理调度,使得m台机器上处理n个作业所需要的总时间最短。
    (1)为给出的作业根据时间数分配机器。将作业按其所需时间的递减顺序排列。一台机器在同一时刻只能处理一个作业,在分配一个作业时,将其分配给最先变为空闲的机器。直到所有作业分配完毕。算出最短调度时间。
    (2)每个作业的所需的时间数和机器数为输入。输出为每个作业所分配的机器(每个机器所完成的作业),以及最短调度时间。

    概要设计

    为给出的作业根据时间数分配机器。将作业按其所需时间的递减顺序排列。一台机器在同一时刻只能处理一个作业,在分配一个作业时,将其分配给最先变为空闲的机器。直到所有作业分配完毕。算出最短调度时间。

    详细设计

    #include<stdio.h>
    #define N 10  //限定机器数和作业数不超过N个
    
    struct MachineNode
    {
    	int ID;  //机器号   
    	int avail;  //机器可用时间 
    };
    struct JobNode
    {
    	int ID;  //作业号 
    	int time;  //处理时间 
    };
    
    void SiftD(JobNode r[], int k, int m)  //建立大根堆  
    {
    	int i, j;
    	i = k;
    	j = 2 * i;
    	while (j <= m)
    	{
    		if (j < m && r[j].time < r[j + 1].time)j++;
    		if (r[i].time > r[j].time)break;
    		else
    		{
    			int temp1, temp2;
    			temp1 = r[i].time;
    			r[i].time = r[j].time;
    			r[j].time = temp1;
    			temp2 = r[i].ID;
    			r[i].ID = r[j].ID;
    			r[j].ID = temp2;
    		}
    	}
    }
    
    void HeapSortD(JobNode r[], int n)
    {
    	for (int i = n / 2; i >= 1; i--)
    		SiftD(r, i, n);
    }
     
    void SiftX(MachineNode r[], int k, int m)  //建立小根堆
    {
    	int i, j;
    	i = k;
    	j = 2 * i;
    	while (j <= m)
    	{
    		if (j<m && r[j].avail>r[j + 1].avail)j++;
    		if (r[i].avail < r[j].avail)break;
    		else
    		{
    			int temp1, temp2;
    			temp1 = r[i].avail;
    			r[i].avail = r[j].avail;
    			r[j].avail = temp1;
    			temp2 = r[i].ID;
    			r[i].ID = r[j].ID;
    			r[j].ID = temp2;
    		}
    	}
    }
    
    void HeapSortX(MachineNode r[], int n)
    {
    	for (int i = n / 2; i >= 1; i--)
    		SiftX(r, i, n);
    }
    
    void assign(MachineNode M[], JobNode J[], int m, int j)  //完成任务分配
    {
    	if (m >= j)  //如果机器数m大于或等于作业数j  
    	{
    		printf("工作数和机器数相同,一台机器完成一个作业\n");
    		HeapSortD(J, j);  //以各作业所需时间建立大根堆,堆顶元素即为最大耗时的作业     
    		printf("最大工作时间为:%d\n", J[1].time);  //最大工作时间即为最大耗时的作业的所需时间 
    	}
    	else  //如果机器数m小于作业数j  
    	{
    		for (int i = 1; i <= m; i++) //先为每台机器分配一个作业,先把所需时间最大的m个作业分配给m台机器。    
    		{
    			HeapSortD(J, j);  //建立大根堆求堆顶元素确定其中耗时最大的作业  
    			M[i].avail = J[1].time;  //机器i的处理时间即为作业的所需时间   
    			printf("机器%d,完成作业%d,时间从0到%d\n", M[i].ID, J[1].ID, M[i].avail);
    			for (int k = 1; k < j; k++)  //减去已分配的作业    
    				J[k] = J[k + 1];
    			j = j - 1;
    		}
    		for (int q = j; j >= 1; q--) //把剩余的j-m个作业分配下去(j=j-m)  
    		{
    			HeapSortX(M, m);  //将m机器个机器按可用时建立小根堆  
    			HeapSortD(J, j);  //将j个作业按处理时间建立大根堆   
    			printf("机器%d,完成作业%d,时间从%d到%d\n", M[1].ID, J[1].ID, M[1].avail, M[1].avail + J[1].time);  //将大根堆的堆顶作业分配给小根堆的堆顶机器   
    			M[1].avail += J[1].time; //将小根堆的堆顶机器加上大根堆的堆顶作业的处理时间,重新插入小根堆(循环执行HeapSortX(M,m)时完成)
    			for (int k = 1; k < j; k++)  //减去已分配的作业  
    				J[k] = J[k + 1];
    			j = j - 1;
    		}
    		printf("最短调度时间为:%d\n", M[1].avail);  //小根堆的堆顶元素就是最短调用时间   
    	}
    }
    
    void main()
    {
    	int j = 0;  //作业个数  
    	int m = 0;  //机器个数  
    	int i;
    	MachineNode M[N];  //机器的结构体数组  
    	JobNode J[N];  //作业的结构体数组
    	printf("作业个数:");
    	scanf_s("%d", &j);
    	for (i = 1; i <= j; i++)
    	{
    		printf("请输入%d个作业需要的处理时间(空格隔开)\n", j);
    		J[i].ID = i;  //为每个作业确定序号  
    		scanf_s("%d", &J[i].time);
    	}
    	printf("机器的个数");
    	scanf_s("%d", &m);
    	for (i = 1; i <= m; i++)
    		M[i].ID = i;  //为每台机器确定序号 
    	assign(M, J, m, j);  //调用完成分配任务的函数 
    }
    
    

    测试与结果

    在这里插入图片描述

    展开全文
  • 机器调度问题java实现

    2011-05-01 11:05:26
    机器调度问题 java 高级算法 研究生课程作业
  • 数据结构程序设计机器调度问题,完整的Word文档,需求分析、解决方案、实现算法和实验结果
  • 机器调度问题 数据结构课设c++.rar ,就是数据结构课设的,没问题
  • 针对单机器生产系统、允许在生产间歇开关机器的可持续调度问题,以最小化碳排放为目标建立数学规划模型,同时对机器的开关机和产品的生产计划进行决策.利用动态规划算法对模型进行求解分析,提出阶段决策最优性条件,并...
  • 针对车间作业调度问题(JSP),本文提出并提出了一种新的启发式算法,目的是最大程度地减少工期。 此方法确定每台机器的作业订单。 评估基于调度规则的组合,例如,每个操作的“最短处理时间”,每个作业的“最早...
  • 小程序~通过大堆栈小堆栈实现的~~实现最优的机器分配问题~~希望能帮到大家~~
  • #include &lt;iostream&gt; #include &lt;cmath&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; using namespace std; const int N = 101;...bool cmp(node a, n...

    #include <iostream>
    #include <cmath>
    #include <vector>
    #include <algorithm>
    using namespace std;
    const int N = 101;
    struct node
    {
        int val;
        int id;
    };
    bool cmp(node a, node b)
    {
        return a.val > b.val;
    }
    int main()
    {
        node a[N], b[N];
        int vis[N];
        int n, m;
        cout << "the number of the work" << endl;
        cin >> n;
        cout << "the time the i's work need" << endl;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i].val;
            a[i].id = i;
        }
        cout << "the number of machines" << endl;
        cin >> m;
        cout << "the time of the ith machinie can work" << endl;
        for (int i = 0; i < m; i++)
        {
            cin >> b[i].val;
            b[i].id = i;
        }
        for (int i = 0; i < n; i++)
            vis[i] = -1;
        sort(a, a + n, cmp);
        sort(b, b + m, cmp);
        /*for (int i = 0; i < m; i++)
            cout << b[i] << " ";
        cout << endl;
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;*/
        for (int i =0;i<m;i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (b[i].val >= a[j].val && vis[a[j].id] == -1)
                {
                    b[i].val -= a[j].val;
                    vis[a[j].id] = b[i].id;
                    cout << b[i].val << endl;
                }
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (vis[i] == -1) cout << "work"<<i<<"cant solve" << endl;
            else cout << "work" << i << "solved by machine" << vis[i] << endl;
        }
        system("pause");
        return 0;
    }
    /*
    5
    7 2 4 5 3
    3
    8 9 6
    */

    展开全文
  • 流水调度问题的Johnson算法: 令N1={ i | ai < bi },N2={ i | ai >= bi }; 将N1中作业按照ai的非递减排序,将N2中作业按照bi的非递增排序; N1中作业和N2中作业相连接构成满足Johnson法则的最优调度。 以上...

    今天训练做到一道题,发现居然有个算法:Johnson调度算法,觉得特别神奇!

    流水调度问题的Johnson算法:
    作业 i 需要走两步:先后进入A、B车间,各花费ai、bi时间,那么:
    令N1={ i | ai < bi },N2={ i | ai >= bi };
    将N1中作业按照ai的非递减排序,将N2中作业按照bi的非递增排序;
    N1中作业和N2中作业相连接构成满足Johnson法则的最优调度。

    以上摘自:http://blog.sina.com.cn/s/blog_7c35df9b0100vga3.html

    即可理解为:
    开始让第二台机器等的时间缩小
    最后让第一台机器等的时间更小

    好啦做题啦:
    题目速递http://poj.org/problem?id=2751

    题意:有n项工作,各项工作需要经过车间A、车间B才ok。求如何安排时间最短。

    根据上述算法,对工作做好安排后,计算花费时间即可。

    (车间A无需等待谁,只需要自己有空就可以开干。而能进入车间B是只有那些已经经过车间A的才可以。)

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<vector>
    #include<string>
    #include<queue> 
    #include<cmath>
    #include<cstring>
    using namespace std;
    #define ll long long
    #define pii pair<int,int>
    #define pll pair<ll,ll>
    const int maxn=1e5+6;
    const int inf=0x3f3f3f3f;
    struct A{
        int x,y;
    }A1[maxn],A2[maxn];
    bool cmp1(A a1,A a2){
        if(a1.x==a2.x)
    	return a1.y<a2.y;
        return a1.x<a2.x;
    }
    bool cmp2(A a1,A a2){
        if(a1.y==a2.y)
    	return a1.x>a2.x;
        return a1.y>a2.y;
    }
    int main(){
        int n;
    	while((scanf("%d",&n)!=EOF)&&n){
            int cnt1,cnt2;
            cnt1=cnt2=0;
            for(int i=0;i<n;i++){
            	int x,y;
                scanf("%d%d",&x,&y);
                if(x<y){
                    A1[cnt1].x=x;
                    A1[cnt1].y=y;
                    cnt1++;
                }
                else{
                    A2[cnt2].x=x;
                    A2[cnt2].y=y;
                    cnt2++;
                }
            }
            sort(A1,A1+cnt1,cmp1);
            sort(A2,A2+cnt2,cmp2);
            int ans1,ans2;
            ans1=ans2=0;
            for(int i=0;i<cnt1;i++){
                 ans1+=A1[i].x;
                 if(ans2<ans1)
                 ans2=ans1+A1[i].y;
                 else
                 ans2+=A1[i].y;
            }
            for(int i=0;i<cnt2;i++){
                 ans1+=A2[i].x;
                 if(ans2<ans1)
                 ans2=ans1+A2[i].y;
                 else
                 ans2+=A2[i].y;
            }
            printf("%d\n",ans2);
        }
    }
    

    说真的特别害怕这种问题,脑袋瓜子最受不住这类题目。。。想半天方法都是猜样例各种猜测。。。就怕码半天还猜错OMG

    展开全文
  • 设第i个作业交给机器A处理时需要时间ai,若由机器B来处理,则需要时间bi。由于各作业的特点和机器性能关系,很可能对于某些i,有ai≧bi,而对于某些j,j i,有aj(a1,a2,a3,a4,a5,a6)=(2,5,7,10,5,2);(b1,b2,b3,b4,...

    用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai,若由机器B来处理,则需要时间bi。由于各作业的特点和机器性能关系,很可能对于某些i,有ai≧bi,而对于某些j,j i,有aj<bj。既不能将一个作业分开由2台机器处理,也没有一台机器能同时处理2个作业。设计一个动态规划算法,使得这2台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。研究一个实例:
    (a1,a2,a3,a4,a5,a6)=(2,5,7,10,5,2);(b1,b2,b3,b4,b5,b5,b6)=(3,8,4,11,3,4)。

    要求:
    输入:输入一个正整数n,表示要处理n个作业。在接下来的2行中,每行有n个正整数,分别表示处理机A和B处理第i个作业需要的处理时间。
    输出:计算出的最短处理时间。

    思路:

    以作业划分阶段, 每个阶段保存2状态:
    1)当前作业在A上完成,且总时间最小时,A,B机器分别的处理的时间;
    2)当前作业在B上完成,且总时间最小时,A,B机器分别的处理的时间;


    具体算法:

    开个整型三维数组保存状态
    第一维表示第几个作业,第二维表示当前作业在那台机器上完成,第三维表示此时A,B的处理时间。
    递推计算即可。

    C++代码
    1. #include <iostream>   
    2. using namespace std;   
    3. int n, mn;   
    4. void allocateMemory(int ***  &x, int rows, int cols, int z) {   
    5.     x = new int **[rows];   
    6.     for (int i = 0; i < rows; ++i) {   
    7.         x[i] = new int *[cols];   
    8.         for (int j = 0; j < cols; ++j)   
    9.             x[i][j] = new int[z];   
    10.     }   
    11. }   
    12. int main() {   
    13.     int *** p;   
    14.     int m = 0;   
    15.     int i, j, k;   
    16.     cin >> n;   
    17.     int *a = new int[n],  *b = new int[n];   
    18.     for (int i = 0; i < n; ++i) {   
    19.         cin >> a[i];   
    20.         if (a[i] > m)   
    21.             m = a[i];   
    22.     }   
    23.     for (i = 0; i < n; ++i) {   
    24.         cin >> b[i];   
    25.         if (b[i] > m)   
    26.             m = b[i];   
    27.     }   
    28.     mn = m * n;   
    29.     allocateMemory(p, mn + 1, mn + 1, n + 1);   
    30.     for (i = 0; i <= mn; ++i)   
    31.     for (j = 0; j <= mn; ++j) {   
    32.         p[i][j][0] = true;   
    33.         for (k = 1; k <= n; ++k)   
    34.             p[i][j][k] = false;   
    35.     }   
    36.     for (k = 1; k <= n; ++k)   
    37.         for (i = 0; i <= mn; ++i)   
    38.     for (j = 0; j <= mn; ++j) {   
    39.         if (i - a[k - 1] >= 0)   
    40.                 p[i][j][k] = p[i - a[k - 1]][j][k - 1];   
    41.         if (j - b[k - 1] >= 0)   
    42.             p[i][j][k] = (p[i][j][k] || p[i][j - b[k - 1]][k - 1]);   
    43.     }   
    44.     int result;   
    45.     for (i = 0, result = mn; i <= mn; ++i)   
    46.         for (j = 0; j <= mn; ++j)   
    47.     if (p[i][j][n]) {   
    48.         int tmp = (i > j) ? i : j;   
    49.         if (tmp < result)   
    50.                 result = tmp;   
    51.     }   
    52.     cout << result << endl;   
    53.     system("pause");   
    54.     return 0;   
    55. }  
    <script type=text/javascript> alimama_pid="mm_10123302_994017_2125239"; alimama_titlecolor="030000"; alimama_descolor ="000000"; alimama_bgcolor="FFFFFF"; alimama_bordercolor="E6E6E6"; alimama_linkcolor="008000"; alimama_bottomcolor="FFFFFF"; alimama_anglesize="4"; alimama_bgpic="0"; alimama_icon="0"; alimama_sizecode="16"; alimama_width=658; alimama_height=60; alimama_type=2; </script> <script src="http://a.alimama.cn/inf.js" type=text/javascript></script> alimamal.php?i=mm_10123302_994017_2125239&u=http%3A%2F%2Fwww.lizhijin.com%2Fview.php%2FWorks%2F132.html&w=658&h=60&re=1280x800&sz=16&r=http%3A%2F%2Fwww.lizhijin.com%2Fview.php%2FWorks%2F133.html&cg=cc4dc810007b29b8ceb0ec279435c1d1&pro=82603016&cas=pro&cah=770&caw=1280&ccd=32&ctz=8&chl=6&cja=1&cpl=0&cmm=0&cf=10.0&sx=300&sy=1930&cbw=1260&cbh=2649
    展开全文
  • 机器调度

    2016-06-18 20:35:00
    我们知道机器调度是计算机科学中一个非常经典的问题。调度问题有很多种,具体条件不同,问题就不同。现在我们要处理的是两个机器的调度问题。 有两个机器A和B。机器A有n种工作模式,我们称之为mode_0,mode_l,...
  • 并行机器最短调度问题

    千次阅读 2015-11-19 20:44:25
    输出:使任务在m台机器并行执行时间最短的一个调度策略 基于贪心选择:选择具有最短任务队列的机器。 #include #include using namespace std; int minTask(int *t,int n){ int tmp = t[0]; int min = 0; for...
  • 以回溯之法子集和问题问题描述代码及思路最佳调度问题问题描述代码及思路部落卫队问题问题描述代码及思路问题描述代码及思路总结 子集和问题 问题描述 代码及思路 最佳调度问题 问题描述 代码及思路 #include...
  • C语言 code blocks能运行,输出工件排序和总加工时间,已知:有n个工件{ J1,J2, …, Jn }需要在一台机器上加工。工件i会有一个到达时刻到达机器处,另已知该工件的加工时长pi。 工件上的约束:每个工件上只可被...
  • 各种机器调度问题在以下方面差别很大:必须满足的约束条件,以及期望得到的调度时间表。现在考虑一个针对2 台机器的机器调度问题。 假设有2台机器,A和B。机器A有n种工作模式,分别称为mode_0, mode_1, …, mode_n-...
  • 对分布式内存机器中相互依赖多任务的优化调度问题,将约束条件归纳为任务约束、链路约束和资源约束,建立了允许任务复制情况下多任务静态调度问题的数学模型.描述了有向无回路图的构造性定义,指出问题一定有不超过...
  • 机器任务调度

    2015-09-15 09:56:14
    随着科学技术的发展,机器已经变得越来越重要了。然而为了以最小的成本换取最大的利益,单台机器上的任务调度问题也越趋成为热点话题。
  • 动态规划—机器调度

    2013-06-19 19:40:45
    用c#写的机器调度算法(动态规划),是算法课程的练习题,对理解动态规划的一类问题还是很有帮助的,书上把主要算法已经列出,所以说对代码本身来说是比较简单的!
  • ★★ 输入文件:machine.in 输出文件:machine.out简单对比时间限制:1 s 内存限制:...我们知道机器调度是计算机科学中一个非常经典的问题。调度问题有很多种,具体条件不同,问题就不同。现在我们要处理的是两个...
  • 经典作业车间调度问题 在传统车间调度模型中,假设工序加工所需要的资源是不具备柔性的资源,工件的所有工序的加工机器是唯一的,且机器顺序是已知的,则可通过确定工序在每台机器上的加工顺序来优化完工时间等系统...
  • 根据具有低碳需求的制造企业的实际情况,建立了考虑机器速度的低碳柔性作业车间调度问题模型。该模型考虑机器加工速度,增加了工件的装夹和卸载时间及机器在不同状态下的碳排放参数,使问题更具现实性。为了实现低碳...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,539
精华内容 615
关键字:

机器调度问题