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

    2018-10-26 22:01:44
    多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 约定:每个作业均可在任何一台机器上加工处理,但未完工前不允许中断处理。作业不能拆分成更小的子作业。 这个...

    多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

    约定:每个作业均可在任何一台机器上加工处理,但未完工前不允许中断处理。作业不能拆分成更小的子作业。

    这个问题是NP完全问题,到目前为止还没有有效的解法。对于这一类问题,贪心选择策略有时可以设计出较好的近似算法。

     

    采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。

    按此策略,当n\leq m时,只要将机器i[0, ti]时间区间分配给作业i即可,算法只需要O(1)时间。

    n> m时,首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)

    #include<iostream>
    #include<stdio.h>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    int a[1005],b[1005];   
    bool cmp(int a,int b){
        return a>b;
    }
    int main(){
        int n,m;
        int T;
        cin>>T;
        while(T--){
            int n,m;
            cin>>n>>m;
            for(int i=0;i<n;i++){
                scanf("%d",a+i);
            }
            memset(b,0,sizeof(b));
            sort(a,a+n,cmp);
            if(n<=m){
                cout<<a[0]<<endl;
                continue;
            }else{
                int sum=0;
                int now=m;
                while(now<n){
                    sum++;
                    int cnt=0;     //cnt是这分钟结束后有几台机器空闲下来
                    for(int i=0;i<now;i++){
                        b[i]++;
                        if(b[i]==a[i]){
                            cnt++;
                        }
                    }
                    now+=cnt;
                }
                int mx=0;
                for(int i=0;i<n;i++){
                    if(a[i]>b[i])
                        mx=max(mx,a[i]-b[i]);    //找出还没做完的工作的最长时间
                }
                cout<<sum+mx<<endl;
            }
        }
        return 0;
    }

     

    展开全文
  • 贪心-多机调度问题

    千次阅读 2016-10-16 14:32:02
    多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 约定,每个作业均可在任何一台机器上加工处理,但未完工前不允许中断处理。作业不能拆分成更小的子作业。 ...

    多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

    约定,每个作业均可在任何一台机器上加工处理,但未完工前不允许中断处理。作业不能拆分成更小的子作业。


      这个问题是NP完全问题,到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。

    采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。

      按此策略,当       时,只要将机器i的[0,ti]时间区间分配给作业i即可,算法只需要O(1)时间。

      当        时,首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)

    例如,设7个独立作业{1,2,3,4,5,6,7}由3台机器M1,M2和M3加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。按算法greedy产生的作业调度如下图所示,所需的加工时间为17。



    展开全文
  • 1、问题描述 设有n个独立的作业{1, 2, …, n}, 由m台相同的机器进行加工处理. 作业i所需时间为t i. 约定:任何作业可以在... 多机调度问题是一个NP完全问题,到目前为止还没有完全有效的解法。对于这类问题,用贪...

    1、问题描述

     设有n个独立的作业{1, 2, …, n}, 由m台相同的机器进行加工处理. 作业i所需时间为t i. 约定:任何作业可以在任何一台机器上加工处理, 但未完工前不允许中断处理,任何作业不能拆分成更小的子作业。要求给出一种作业调度方案,使所给的n 个作业在尽可能短的时间内由m台机器加工处理完成。 
    
     多机调度问题是一个NP完全问题,到目前为止还没有完全有效的解法。对于这类问题,用贪心选择策略有时可以设计出一个比较好的近似算法。
    
     2、贪心算法求解思路
    
     采用最长处理时间作业优先的贪心策略:
     当n≤m时, 只要将机器i的[0, ti]时间区间分配给作业i即可。
     当n>m时, 将n个作业依其所需的处理时间从大到小排序,然后依次将作业分配给空闲的处理机。
    
      具体代码如下:
    

    package 贪心;
    
    //public class Greedy
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.List;
    
    /**
     * @author 葛帅帅
     */
    public class Greedy {
        public static class JobNode implements Comparable{
            int id;//作业的标号
            int time;//作业时间
            public JobNode(int id,int time){
                this.id=id;
                this.time=time;
            }
            @Override
            public int compareTo(Object x) {//按时间从大到小排列
                int times=((JobNode)x).time;
                if(time>times) return -1;
                if(time==times) return 0;
                return 1;
    
            }
        }
        public static class MachineNode implements Comparable{
            int id;//机器的标号
            int avail;//机器空闲的时间(即机器做完某一项工作的时间)
            public MachineNode(int id,int avail){
                this.id=id;
                this.avail=avail;
            }
            @Override
            public int compareTo(Object o) {//升序排序,LinkedList的first为最小的
                int xs=((MachineNode)o).avail;
                if(avail<xs) return -1;
                if(avail==xs) return 0;
                return 1;
            }
        }
        public static int greedy(int[] a ,int m){
            int n=a.length;//a的下标从1开始,所以n(作业的数目)=a.length-1
            int sum=0;
            if(n<=m){
                for(int i=0;i<n;i++)
                    sum+=a[i+1];
                System.out.println("为每个作业分别分配一台机器");
                return sum;
            }
            List<JobNode> d=new ArrayList<JobNode>();//d保存所有的作业
            for(int i=0;i<n;i++){//将所有的作业存入List中,每一项包含标号和时间
                JobNode jb=new JobNode(i+1,a[i]);
                d.add(jb);
            }
            Collections.sort(d);//对作业的List进行排序
            LinkedList<MachineNode> h=new LinkedList<MachineNode>();//h保存所有的机器
            for(int i=1;i<=m;i++){//将所有的机器存入LinkedList中
                MachineNode x=new MachineNode(i,0);//初始时,每台机器的空闲时间(完成上一个作业的时间)都为0
                h.add(x);
            }
            int test=h.size();
            for(int i=0;i<n;i++){
                  Collections.sort(h);
                MachineNode x=h.peek();
                System.out.println("将机器"+x.id+"从"+x.avail+"到"+(x.avail+d.get(i).time)+"的时间段分配给作业"+d.get(i).id);
                x.avail+=d.get(i).time;
                sum=x.avail;
            }
            return sum;
        }
        public static void main(String[] args) {
            int[] a={14,2,3,4,5,6,8,8,9};
                  // 1,2,3,4,5,6,7 ,8,9
            int m=3;
            int sum=greedy(a,m);
            System.out.println("总时间为:"+sum);
        }
    }
    /**
     运行结果:
     将机器1从0到14的时间段分配给作业1
     将机器2从0到9的时间段分配给作业9
     将机器3从0到8的时间段分配给作业7
     将机器3从8到16的时间段分配给作业8
     将机器2从9到15的时间段分配给作业6
     将机器1从14到19的时间段分配给作业5
     将机器2从15到19的时间段分配给作业4
     将机器3从16到19的时间段分配给作业3
     将机器3从19到21的时间段分配给作业2
     总时间为:21
     */
    
    
    展开全文
  • 问题描述 设有n个独立的作业{1,2,…,...多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 问题求解 贪心法求解多机调度问题的贪心策略是最长处理时间作业优先,...

    问题描述

    设有n个独立的作业{1,2,…,n},由m台相同的机器{1,2, …,m}进行加工处理,作业i所需的处理时间为ti(1≤i≤n),每个作业均可在任何一台机器上加工处理,但未完工前不允许中断,任何作业也不能拆分成更小的子作业。
    多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

    问题求解

    贪心法求解多机调度问题的贪心策略是最长处理时间作业优先,即把处理时间最长的作业分配给最先空闲的机器,这样可以保证处理时间长的作业优先处理,从而在整体上获得尽可能短的处理时间。
    按照最长处理时间作业优先的贪心策略,当m≥n时,只要将机器i的[0,ti)时间区间分配给作业i即可;
    当m<n时,首先将n个作业依其所需的处理时间从大到小排序,然后依此顺序将作业分配给空闲的处理机。

    代码

    int n = 7;
    int m = 3;
    struct NodeType
    {
    	int no;
    	int t;
    	int mno;//机器序号
    	bool operator<(const NodeType &s)const//按照处理时间递减排序
    	{
    		return t > s.t;
    	}
    };
    
    struct NodeType A[] = { {1,2},{2,14},{3,4},{4,16},{5,6},{6,5},{7,3} };
    
    void solve()
    {
    	NodeType e;
    	if (n <= m)
    		return;
    	sort(A, A + n);
    	priority_queue<NodeType> qu;
    	for (int i = 0; i < m; i++)//给每个机器分配一个作业
    	{
    		A[i].mno = i + 1;
    		qu.push(A[i]);
    	}
    	for (int j = m; j < n; j++)//分配余下的作业
    	{
    		e = qu.top();
    		qu.pop();
    		e.t += A[j].t;
    		qu.push(e);
    	}
    }
    

    算法分析

    排序的时间复杂度为O(nlog2n),两次for循环的时间合起来为O(n),所以本算法的时间复杂度为O(nlog2n)。

    展开全文
  • 贪心算法多机调度问题
  • 多机调度问题-贪心算法

    千次阅读 2016-05-13 08:06:41
    设有n个独立的作业{1, 2, …, n}, 由m台相同的机器进行加工处理. 作业i所需时间为t i....多机调度问题是一个NP完全问题,到目前为止还没有完全有效的解法。对于这类问题,用贪心选择策略有时可以设
  • 多机调度问题 利用贪心法设计算法求解如下问题: 要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定,每个作业均可在任何一台机器上加工处理,但未完工前不允许中断处理。...
  • 贪心算法-多机调度问题

    千次阅读 2018-10-30 17:22:49
    多机调度问题: 有n个独立的作业需要在m台相同的机器上进行加工处理. 作业i需要的加工时间为ti. 每个作业可以任选一台机器加工, 但加工结束前不能中断, 作业不允许拆分. 要求给一种作业调度方案, 使所给的n个作业在...
  • 【贪心法】多机调度问题

    千次阅读 多人点赞 2019-07-15 15:24:28
    问题描述   设有n个独立的作业{1, 2, …, n},由m台相同...多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。   设7个独立作业{1, 2, 3, 4, 5...
  • 多机调度问题(贪心)

    千次阅读 2013-03-08 22:33:41
    算法设计例题:多机调度问题(贪心) memory limit: 32768KB time limit: 1000MS accept: 9 submit: 19 Description 设有n个独立的作业{1,2,…,n},由m台相同的机器进行加工处理。作业i所需...
  • 贪心算法-多机调度问题C++

    千次阅读 2020-06-05 00:34:28
    贪心算法-多机调度问题C++ 1.问题 要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定,每个作业均可在任何一台机器上加工处理,但未完工前不允许中断处理。作业不能拆分成更...
  • 多机调度问题--贪心策略

    千次阅读 2019-08-03 19:03:11
    题目:设有n个独立的作业,由m台相同的计算机进行加工。作业 i 的处理时间为 ti ,每个...求解多机调度问题的贪心策略是最长处理时间的作业优先,即把处理时间最长的作业分配给最先空闲的计算机。 input 第一行T(1...
  • 多机调度问题--初谈贪心算法(一)

    万次阅读 2018-11-22 18:50:45
    初步学习贪心算法,这里以这道题来进行学习,话不说,下面给出题目:多机调度问题 题目:  某工厂有n个独立的作业,由m台相同的机器进行加工处理。作业i所需的加工时间为ti,任何作业在被处理时不能中断,也不...
  • 多机调度问题描述 输入: n个独立的作业{1,2,3,4,5,6,…n},作业i所需要的处理时间为ti m台机器,任何作业可以在任何机器上完成,但作业的处理不允许中断 输出: 最优的作业调度方案,使得n个作业在尽可能短的时间内...
  • 1、问题描述  设有n个独立的作业{1, 2, …, n}, 由m台相同的机器进行加工处理. 作业i所需时间为t i. 约定:任何作业可以在任何一台机器上加工... 多机调度问题是一个NP完全问题,到目前为止还没有完全有效的解法。
  • 贪心算法之多机调度问题

    千次阅读 2012-06-02 12:08:28
    问题描述: ...多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 这个问题是NP完全问题,到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略
  • 多机调度问题的贪心解法

    千次阅读 2012-02-15 10:25:15
    多机调度问题: 有n个独立的作业需要在m台相同的机器上进行加工处理. 作业i需要的加工时间为ti. 每个作业可以任选一台机器加工, 但加工结束前不能中断, 作业不允许拆分. 要求给一种作业调度方案, 使所给的n个作业在...
  • 算法分析: 采用最长处理时间作业优先的贪心选择策略,可以设计出解多机调度问题较好的近似算法。分n(作业数小于机器数),n>m(作业数大于机器数)求解。假定有7个独立作业,所需处理时间分别为{2,14,4,16,6,5,...
  • 多机调度问题(贪心法)

    千次阅读 2013-06-09 19:07:34
    题目:  设有n个独立的作业{1, ...多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。     伪代码为: 将数组t[n]由大到小排序,对应的作业序号存储在数组p[n]中;
  • 算法之多机调度问题

    千次阅读 2018-05-22 21:05:56
    要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。2.问题分析:该问题是NP完全问题,使用贪心选择策略可以得到较好的近似算法,贪心选择策略:最长处理时间作业优先...
  • 完全NP问题的一种未证明解法,由多机调度问题引例得到。希望得到关注。
  • 多机调度问题(贪心算法)

    千次阅读 2020-12-13 16:55:03
    m时,首先将n个作业从大到小排序,然后依此顺序将作业分配给空闲 的处理。也就是说从剩下的作业中,选择需要处理时间最长的,然后依次选择处理时间次长的,直到所有的作业全部处 理完毕,或者机器不能再处理其他...
  • 贪心之多机调度问题

    千次阅读 2015-08-19 12:09:11
    1、问题描述  设有n个独立的作业{1, 2, …, n}, 由m台相同的机器进行加工处理. 作业i所需时间为t i. 约定:任何作业可以在任何一台机器上加工处理, 但未完工前不允许中断处理,任何作业不能拆分成更小的子作业。...
  • 贪心法_多机调度问题

    千次阅读 2005-10-22 22:14:00
    设有 n 个独立的作业 { 1 , 2 , .....多机调度问题要求给出一种作业调度方案,使所给的 n 个作业在尽可能短的时间内由 m 台机器加工处理完成。分析:这个问题是一个NP完全问题,到目前为止还没有一个有效的解法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 264,264
精华内容 105,705
关键字:

多机调度问题