体能测试时间安排优化模型摘要本文讨论了一类时间表优化问题。

首先，我们根据机器测试时间和台数求得所需总时间段数的下届为4。

在同一个班级人数不进行分组的前提下，将56个班级分成19个小组，计算出每个小组测试完所有项目所需的时间。

然后建立了0-1规划模型，将这19个小组的时间段放入每天的两个测试时间段内，使得全部放完这19个小组的时段所需要的总测试时间段数最少，并求得最少测试时间段数恰好为下届4段。

其次，为了节省学生等待时间，我们将每个班级人数进行分组，每组为20人，共分成103组。

由于这20人最多来自两个不同的班级，我们求得完成20人的时间只可能为425秒、430秒、435秒这三种情况。

这样将原来问题转化为怎样用最少时间段数放入102个435秒。

通过求解得到的时间段数为4段，，等待时间最长的同学仅需等待分钟，从而说明了分组的必要。

最后，通过给出了每项测试的人均时间应该相等的结论，用来配置机器台数，并讨论了场地容量对所需时段和等待时间的影响。

关键词：等待时间时间段数时间等级分组一、问题重述某校按照教学计划安排各班学生进行体能测试，以了解学生的身体状况。

测试包括身高与体重、立定跳远、肺活量、握力和台阶试验共5个项目，均由电子仪器自动测量、记录并保存信息。

该校引进身高与体重测量仪器3台，立定跳远、肺活量测量仪器各1台，握力和台阶试验测量仪器各2台。

身高与体重、立定跳远、肺活量、握力4个项目每台仪器每个学生的平均测试（包括学生的转换）时间分别为10秒、20秒、20秒、15秒，台阶试验每台仪器一次测试5个学生，需要3分30秒。

每个学生测试每个项目前要录入个人信息，即学号，平均需时5秒。

仪器在每个学生测量完毕后学号将自动后移一位，于是如果前后测试的学生学号相连，就可以省去录入时间，而同一班学生的学号是相连的。

学校安排每天的测试时间为8：00－12：10与13：30－16：45两个时间段。

5项测试都在最多容纳150个学生的小型场所进行，测试项目没有固定的先后顺序。

参加体能测试的各班人数见附表。

学校要求同一班的所有学生在同一时间段内完成所有项目的测试，并且在整个测试所需时间段数最少的条件下，尽量节省学生的等待时间。

请你用数学符号和语言表述各班测试时间安排问题，给出该数学问题的算法，尽量用清晰、直观的图表形式为学校工作人员及各班学生表示出测试时间的安排计划，并且说明该计划怎样满足学校的上述要求和条件。

最后，请对学校以后的体能测试就以下方面提出建议，并说明理由：如引进各项测量仪器的数量；测试场所的人员容量；一个班的学生是否需要分成几个组进行测试等。

二、问题分析首先，我们在不考虑将一个班级的学生分成几个小组的情况下，求解最小的时间段数和学生等待时间。

通过对机器台数、每个项目测试时间和场地容量等因素的分析计算，我们将所有的56个班级人数划分成19个小组，其中最后一个小组只有2个班级，其余小组的班级数量均为3。

并且，每个小组内的班级人数比较接近，这样可以减少等待时间。

我们算出每个小组测试所需要的最少时间，然后将19个小组的时间段进行合理组合，以便得到最少的时间段数能包含这所有的19个时间段。

其次，在保证时间段数最少的情况下，若我们将同一班级人数进行合理的分组，按照我们定义的等待时间，没有进入测试场所的同学不算是等待，这样可较大程度上节约学生的等待时间，从而说明分组是必要的。

三、模型假设和符号约定（1）忽略人员进入和离开测试场地所用时间；（2）假设学生等待时间指该生进入测试场地后开始的等待时间，不考虑其在未进入测试场地之前的时间；（3）把身高与体重、立定跳远、肺活量、握力、台阶实验测试分别称为第一、二、三、四、五项测试；（4）五个测试项目没有先后顺序；（5）任何班级的学生做完所有测试即可离开场地；T——第i轮测试所花费的时间；（6）in——第i个班级的人数。

（7）i四、模型的建立与求解由于56个班级的总人数为2036，假设每台机器不停止工作，所有人完成第一项测试至少需要2036×10÷3+56×5=（s）。

同理可得所有人完成第二、三、四、五项测试至少需要的时间分别为41000、41000、15550、43036秒。

那么，至少需要43036秒才能让所有人完成全部的测试项目。

由于时间段长一次为15000秒、11700秒，因此至少需要4个时间段才能完成所有人的测试项目，即时间段的下届为4段。

在不对单个班级进行分组的前提下，由于第五项每次可以测5名学生，且有两台机器，则对不同班级的总人数，可得班级测试完第五项所需时间分布表：班级人数为n 时测试台阶实验所需时间计算公式为：t=⎥⎥⎤⎢⎢⎡10n +5 定义：在只进行第五项测试时，把所有人数可能不同但测试完第五项所需时间相同的班级称为一个时间等级。

例如：班级人数为35和40的两个班级分别做完第五项测试所用时间均为845秒，那么按照，这两个班级为同一时间等级。

命题1：假设同一班级的人数不在进行分组，若每次同时进入测试场地的班级数为3，且每个班级的人数不小于17人时，那么有：同时进入场地的3个班级全部完成第二项、第三项、第五项测试所需时间与这3个班级完成所有五项测试所需时间相同。

证明： 假设同时入场的班级分别为1c 、2c 、3c ，其人数分别为1n 、2n 、3n 。

（1） 现让这三个班级分别去做第二、三、五项测试，这三个班级都已经完成各自的测试称为第一轮；（2） 第一轮测试完成后，让1c 班去做第三项测试，让2c 班去做第五项测试，让3c 班去做第二项测试，这三个班级都已经完成各自的测试称为第二轮；（3） 第二轮结束后，依次类推，让1c 班去做第五项测试，让2c 班去做第二项测试，让3c 班去做第三项测试，这三个班级都已经完成各自的测试称为第三轮。

如表2所示：在第一轮中，1c 班的第一个学生在做完第二项测试后，该同学完全可以利用等待该班第二位同学的第二项测试的时间去进行第一项测试（共需要10+5秒），而当他测试完第二项时，1c 班第二位同学依然在进行第二项测试，而此时1c 班的第一个同学再去做第四项测试，由于1c 班的人数不小于17，因此1c 班还有部分同学尚未完成第二项测试。

1c 班的第二个同学完全按照该班第一个同学的路线进行，以此类推。

那么该班级除了后两位同学，其余均可以在1c 班全部测完第二项之前，也完成第一、四项的测试。

倒数后两位可以在第二轮开始，即1c 进行第三项测试时，离开1c 班队列去做完第一、四项测试，然后回到对列继续等待第三项测试。

由于第三项测试的机器为三台，第四项测试的机器为二台，完全足够，并且在第一轮中1c 和2c 班分别做第二、三项的时间均为20秒每人，2c 班的同学的路线与1c 班相似。

对于3c 班也可以在第一、二、三轮测试的间隙完成第一、四项的测试。

另外，第二、三项测试需要20秒，而第五项测试序言210秒，但可以同时测试5人且有2台机器，那么人均耗时约为21秒。

并有以上的命题讨论我们知道若三个班级的人数相差不大，则比较节约时间，因此我讲56个班级分组，每组的班级同时入场。

情况一：若该组中的三个班级人数为1n 、2n 、3n 均处于同一时间等级，则完成第一轮测试所需时间为：1T =210•⎥⎥⎤⎢⎢⎡101n +5 （这里「」是上取整数函数）； 这是因为若班级人数1n 、2n 、3n 处于同一时间等级，则显然有：20×2,1max =i {}≤i n 210×⎥⎥⎤⎢⎢⎡101n ； 再加上第一位同学录入学号的5秒，则完成第一轮总共所需时间为：1T =210•⎥⎥⎤⎢⎢⎡101n +5 同理可得第二、三轮时间分别为2T =210•⎥⎥⎤⎢⎢⎡102n +5和3T =210•⎥⎥⎤⎢⎢⎡103n +5; 则完成三轮测试所需的时间为：T =1T +2T +3T =∑=•31210i 「10i n 」+15 （1） 有上面的分组我们可以知道除了第6、19两组，其他分组均出在同一时间等级，可按照（1）式计算完成时间（结果见表5）情况二：若三个班级不全处于同一时间等级，则由于人数不同有多种情况出现，具体情况时具体计算这里不给出计算公式。

表3中有两组的班级不同一时间等级，这两组为第6组和第19组。

现在分别计算器完成时间：测试所需的总时间T=4695秒。

综合上面两种情况，我们得到所有组合做完全部测试的时间如下表所示：使得所需的总时间段数最少。

设n 表示所需的时间段总数，i t 表示表5中第i 个组合所需时间，j s 表示第j 个时间段长度，其中i =1，2，...19；j =1，2，...n .显然有：j s =⎩⎨⎧.11700,15000段，若这个时段为下午时；若这个时段为上午时段， 进一步假设0-1变量j i c ,:j i c ,=⎩⎨⎧，反之个时间段；组被分配到第若第0,1j i ，其中i =1，2，...19；j =1，2，...n .即得到0-1规划模型一：min n ,..t s ∑=nj j i c 1,=1; i =1,2, (19)j i i j i s t c ≤•∑=191,; j =1，2，...n .上述模型中：第一个约束表示每个组能且只能安排在某一时段;第二个约束表示安排进任一时段的所有组的测试总时间必不大于该时段长度。

利用LINGO 编程解得结果如下：4，故以上结果为最优方案。

对于以上的方案，基于假设（2）和（5），每个组最后一名离开的同学（在该组中等待时间最长）等待时间完全由分组情况决定，与该组进入次序无关。

因为最后一名同学的等待时间即为该组所需时间减去275秒（每个同学完成五项测试的时间）。

则由表5可得，每组等待时间最长的同学的等待时间。

第一组最后一名同学总等待时间为1275-275=1000秒；第19组最后一名同学总等待时间为4420秒（约个小时）。

等待时间较长，需要改进.当班级人数较多时，若不对同一个班级的学生分组会使得学生的等待时间较长。

为了减少学生的等待时间，可以将同一个班级人数分组进入场地进行测试。

现在考虑对同一班级学生进行分组的情况。

命题2：若每次同时进入场地的人数为20人，且这20人学好顺序相连，则完成这20人全部的5项测试最少需要425秒，且可以达到425秒。

证明：首先证明至少425秒。

因为即使不考虑其他4项，只做完第五个项目，这20人就需要425秒（见表1）。

其次证明可以达到425秒。

我们假设这20人的学号次序为从1到20，则让学号为1到5的学生测试第一台台阶试验机，与此同时让学号为6到10的学生测试立定跳远，让学号为11到15的同学测试第二台台阶实验机，让学号为16到20的同学测试肺活量。

如下图所示：立定跳远肺活量台阶实验台阶实验学号学号号与6105秒）。