单台机器上任务调度问题

 

摘要：本文构建了单机任务调度问题中分别以完成任务时间最小、平均处理任务最小和总超时时间最小为准则下的非线性通用数学模型，具有统一的推广性。并在此基础上，提出了程序效率改进的建议。最后得出结果：对于问题1，完成所有任务总需时的最小值是31；对于问题2，平均处理任务时间的最小值是12.85714；对于问题3，总超时为32。

关键词：单台机器；任务调度；数学模型

1 问题重述

   一台机器处理一批任务，任务执行不可打断。任务的发布时刻，持续时间，规定完成时间如下图所示，

      

任务	发布时刻	持续时间	规定完成时刻
1	2	5	10
2	5	6	21
3	4	8	15
4	0	4	10
5	0	2	5
6	8	4	15
7	9	2	22

表1 

   要求构建数学模型，分别求完成所有任务所需时最小值、平均处理任务时间的最小值和总超时时间的最小值。

2 基本假设

  （1）机器运行期间稳定好，没有内在和外来的故障发生。

  （2）机器可等待任务，亦可连续执行任务且任务切换所需时间忽略不计。

  （3）任务不能在发布时刻之前执行。

  （4）任务可超时执行且不影响机器继续执行。

3 符号说明

 

4 问题分析

单机调度问题可直观的表示为如下图：

图1

任务持续时间 为线上标注所示。

问题1，完成所有任务总需时应该从0时刻计时，求最后所有任务完成的时刻。为此，可能出现几种不同的情况：（1）任务发布时间~任务实际完成时间所构成的集合没有交集；（2）任务发布时间~任务实际完成时间所构成的集合有交集。

对于情况（1），当某个任务执行完毕后，则由假设2和3，机器必需等待；对于情况（2），则由假设2，有交集处，机器连续执行且任务切换时间忽略不计。

问题2，平均处理任务是指任务发布时间到任务完成时刻这段时间。

问题3，总超时时间是指，如果某个任务没有超时，则超时时间为0；如果某个任务超时，则超时时间为规定完成时刻到任务实际完成时刻这段时间。总超时时间为超时时间之和。

为此，解决上述问题，必然要解决两个基本问题。

定理1

定理2

5 模型建立

  由问题分析，可建立如下模型：

  问题1，

  问题2，

  问题3，

    6 模型求解

       利用LINGO 9.0，对以上问题进行求解。其程序代码和数据结果如下：

       问题1，

       model:

   sets:

   task/1..7/:G,ts,tp,tc,C;!集合/成员（属性下标）/属性;

   endsets

   data:

   G=2 5 4 0 0 8 9;

   tp=5 6 8 4 2 4 2;

   C=10 21 15 10 5 15 22;

   enddata

   min=@smax(tc(1),tc(2),tc(3),tc(4),tc(5),tc(6),tc(7));

   @for(task(i):ts(i)>=G(i));

   @for(task(i):tc(i)=ts(i)+tp(i));

 @for(task(i):@for(task(j)|j #gt# i:(ts(j)-tc(i))*(ts(i)-tc(j))<=0));

!for中嵌套for;

End

结果1，(仅给出未知数的值，下同)

Objective value:                              31.00000

TS( 1)        14.00000            0.000000

                         TS( 2)        25.00000            0.000000

                         TS( 3)        6.000000            0.000000

                         TS( 4)        2.000000            0.000000

                         TS( 5)        0.000000            0.000000

                         TS( 6)        21.00000            0.000000

                         TS( 7)        19.00000            0.000000

TC( 1)        19.00000            0.000000

                         TC( 2)        31.00000            0.000000

                         TC( 3)        14.00000            0.000000

                         TC( 4)        6.000000            0.000000

                         TC( 5)        2.000000            0.000000

                         TC( 6)        25.00000            0.000000

                         TC( 7)        21.00000            0.000000

 

问题2，

model:

   sets:

   task/1..7/:G,ts,tp,tc,C;!集合/成员（属性下标示）/属性;

   endsets

   data:

   G=2 5 4 0 0 8 9;

   tp=5 6 8 4 2 4 2;

   C=10 21 15 10 5 15 22;

   enddata

   min=@sum(task(i):(tc(i)-G(i))/7);!目标函数二;

   @for(task(i):ts(i)>=G(i));

   @for(task(i):tc(i)=ts(i)+tp(i));

   @for(task(i):@for(task(j)|j #gt# i:(ts(j)-tc(i))*(ts(i)-tc(j))<=0));

   !for中嵌套for;

End

结果2：

   Objective value:                              12.85714

TS( 1)        14.00000            0.000000

                         TS( 2)        25.00000            0.000000

                         TS( 3)        6.000000            0.000000

                         TS( 4)        2.000000            0.000000

                         TS( 5)        0.000000            0.000000

                         TS( 6)        21.00000            0.000000

                         TS( 7)        19.00000            0.000000 

                         TC( 1)        19.00000            0.000000

                         TC( 2)        31.00000            0.000000

                         TC( 3)        14.00000            0.000000

                         TC( 4)        6.000000            0.000000

                         TC( 5)        2.000000            0.000000

                         TC( 6)        25.00000            0.000000

                         TC( 7)        21.00000            0.000000

 

问题3，

 

model:

   sets:

   task/1..7/:G,ts,tp,tc,C;!集合/成员（属性下标示）/属性;

   endsets

   data:

   G=2 5 4 0 0 8 9;

   tp=5 6 8 4 2 4 2;

   C=10 21 15 10 5 15 22;

   enddata

   min=@sum(task(i):@abs(tc(i)-C(i))/2-(tc(i)-C(i))/2);!目标函数三;

   @for(task(i):ts(i)>=G(i));

   @for(task(i):tc(i)=ts(i)+tp(i));

   @for(task(i):@for(task(j)|j #gt# i:(ts(j)-tc(i))*(ts(i)-tc(j))<=0));

   !for中嵌套for;

end

结果3：

Objective value:                              32.00000

                 TS( 1)        6.000000            0.000000

                         TS( 2)        11.00000            0.000000

                         TS( 3)        17.00000            0.000000

                         TS( 4)        2.000000            0.000000

                         TS( 5)        0.000000            0.000000

                         TS( 6)        27.00000            0.000000

                     TS( 7)        25.00000            0.000000

                     TC( 1)        11.00000            0.000000

                         TC( 2)        17.00000            0.000000

                         TC( 3)        25.00000            0.000000

                         TC( 4)        6.000000            0.000000

                         TC( 5)        2.000000            0.000000

                         TC( 6)        31.00000            0.000000

                         TC( 7)        27.00000            0.000000

 

7 结果分析及算法改进

   由图1，可直观的得出问题1的结果是正确的，另外其他两个问题也都可以直观的推算出来。

从Lingo 9.0的使用过程中，推知，软件采用了迭代算法来求解最值.由限制条件分析可得，应尽量消除二次项。为此，通过查阅文献，对于大量的数据，可采用启发式算法进行逻辑计算，从而快速求解。

本文构建了单机调度任务不可中断的数学模型，具有普通的适用性，在数据解算上仍需要智能的算法来计算，来求得高效准确的数据结果。

 

参考文献

 

[1] 谭永基等编著.数学模型[M].复旦大学出版社.2005.

[2] 李凯，马华伟，杨善林.含作业到达时间的单机调度问题的改进算法[J].中国机械工程.2008,(08).

[3] 湖北大学生数学建模竞赛专家组.数学模型（本科册）[M].华中科技大学出版社.2006.

[4] 李志江，李国欣，张敏，中国矿业大学数模教练组.管道订购与运输问题[j].数学实践与认知.2001,(1).

[5] 汪国强.数学建模优秀案例选编[M].华南理工大学出版社.1998