任务调度问题实验_贪心算法求解单机任务调度问题,总惩罚最小

一、问题描述

　　在单处理器上具有期限和惩罚的单位时间任务调度问题。

二、算法原理

　　任务调度问题就是给定一个有穷单位时间任务的集合S，集合S中的每个任务都有一个截止期限d_i和超时惩罚w_i，需要找出集合S的一个调度，使得因任务误期所导致的总惩罚最小，这个调度也称为S的一个最优调度。

　　实现任务的最优调度主要就是利用贪心算法中拟阵的思想。如果S是一个带期限的单位时间任务的集合，且I是所有独立的任务集构成的结合，则对应的系统M=（S，I）是一个拟阵。利用拟阵解决任务调度问题的算法原理主要就是将最小化迟任务的惩罚之和问题转化为最大化早任务的惩罚之和的问题，也就是说在任务调度的时候优先选择当前任务序列中惩罚最大的任务。这里，假设集合A存放任务的一个调度。如果存在关于A中任务的一个调度，使得没有一个任务是迟的，称任务集合A是独立的。实现该问题的贪心算法如下：

　　A <- Ø

　　Sort S[M] into monotonically decreasing order by w

　　for each x∈S[M]

     　　do if AU{x} ∈ I[M]

          　　then A <- AU{x}

　　初始时A为空集，然后对S中的所有任务按惩罚大小降序排序，然后进入循环。循环的过程中依次访问S的中所有任务，然后进行独立性检查，如果当前任务x加入集合A之后A依然是独立的，则将A置为AU{x}，否则检查下一个任务直到扫描结束，最后所得到的集合A即是一个最优子集，然后进行相应的调整得到最后的输出。

三、实验数据

　　（1）任务调度问题的输入：

　　　　a)    任务的数量n，即表示当前任务集合S={a1,a2,a3……an}；

　　　　b)   n个任务的期限d1,d2,d3……dn，每个任务的di满足1≤ di ≤n，且任

　　　　　　务要求ai在di之前完成；

　　　　c)    n个任务的权（惩罚）w1,w2,w3……wn。表示任务ai如果没在时间di

　　之前完成，则导致惩罚wi，如果任务在期限之前完成，则没有惩罚; 同时在本实验中，还会将每个wi值替换为max{w1,w2,w3……wn}-wi，并运行算法进行第二次实验，然后比较两次实验所得结果。

　　在本次实验中，n取值为7，每个任务的期限为4,2,4,3,1,4,6，对应的惩罚为70,60,50,40,30,20,10。

　　（2）任务调度问题的输出：

　　　　a)     贪心算法所选的任务以及放弃的任务，所选的任务即表示最终会在期限

　　　　　　内完成的任务。放弃的任务表示最终会因误期而受到惩罚的任务。

　　　　b)     最终的最优调度序列

　　　　c)     最优调度所带来的总的惩罚数

四、实验截图

　　

五、源代码

　　

#include <stdio.h>
#include <stdlib.h>
 
void swap(int *x, int *y)
{
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
/*任务调度算法,满足拟阵性质，利用GREEDY贪心策略*/
/*期限序列d[], d1,d2……dn*/
/*惩罚序列w[], w1,w2……wn*/
/*任务个数n*/
void taskSchedule(int *d, int *w, int n)
{
    int i = 0;
    int j = 0;
    int k = 1;                           
    int s = 0;
    int t = 1;                                  
    int a[n+1];                                
    int b[n+1];                                
    int sn[n+1];                               
    int flag = 0;                             
    int count = 0;                           
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    for(i = 0; i <= n; i++)
    {
        sn[i] = i;
    }
 
    for(i = 1; i < n; i++)
    {
        for(j = i + 1; j <= n; j++)
        {
            if(w[sn[i]] <= w[sn[j]])
            {
                swap(&sn[i], &sn[j]);
            }
        }
     }
     k = 1;
 
     for(i = 1; i <= n; i++)
     {
 
         flag = 0;
         a[k] = sn[i];
         for(j = 1; j <= k; j++)
         {
             count = 0;
             for(s = 1; s <= k; s++)
             {
                 if(d[a[s]] <= j) count++;
             }
             if(count > j)
             {
                 flag = 1;
                 break;
             }
         }
         if(flag == 1)
         {
             b[t] = sn[i];
             a[k] = 0;
             t++;
         }
         else
         {
             k++;
         }
     }
 
     if(b[t] == 0) t--;
     if(a[k] == 0) k--;
 
     printf("\n贪心算法选择了任务：\n");
     //printf("k==%d\n",k);
     for(i = 1; i <= k && i<=n; i++)
        printf("a%d  ",a[i]);
     printf("\n");
     printf("放弃了任务：\n");
     int w_sum = 0;
     //printf("t==%d\n",t);
     for(i = 1; i <= t  && i <= n ; i++)
     {
         printf("a%d  ",b[i]);
         w_sum = w_sum + w[b[i]];
     }
 
     int temp = 0;
     for(i = 2; i <= k; i++)
     {
         temp = a[i];
         s = i - 1;
         while(s < n && s >= 1 && d[temp] < d[a[s]])
         {
             a[s+1] = a[s];
             s--;
         }
         a[s+1] = temp;
     }
 
     for(i = 1; i <= t; i++)
     {
         k++;
         a[k] = b[i];
     }
     printf("\n最终的最优调度为：\n");
     for(i = 1; i <= k && i <= n; i++)
        printf("a%d  ", a[i]);
     printf("\n总的惩罚数为：%d\n", w_sum);
}
 
int main()
{
    int n = 0;
    int i = 0;
 
    printf("请输入任务个数:\n");
    scanf("%d", &n);
 
    int *d = (int *) malloc ((n+1) * sizeof(int));
    printf("请输入每个任务的期限\n");
    d[0] = 0;
    for(i = 1; i < n+1; i++)
    {
        scanf("%d", &d[i]);
    }
    for(i = 1; i  < n+1; i++)
    {
        if(d[i] > n)
        {
            printf("\n任务a%d的期限非法，请重新输入:",i);
            scanf("%d", &d[i]);
        }
    }
 
    int *w = (int *) malloc ((n+1) * sizeof(int));
    printf("\n请输入每个任务的惩罚:\n");
    w[0] = 0;
    for(i = 1; i < n+1; i++)
    {
        scanf("%d", &w[i]);
    }
    taskSchedule(d, w, n);
    printf("\n\n使用max{w}-wi替换wi后的各任务惩罚为：\n");
    int max = 0;
    for(i = 1; i <= n; i++)
        if(w[i] > max)
            max = w[i];
    for(i = 1; i <= n; i++)
    {
        w[i] = max - w[i];
        printf("%d  ",w[i]);
    }
    printf("\n\n算法运行结果为：");
    taskSchedule(d, w, n);
    system("pause");
    return 0;
}