快件全部三问思路.docx

一、问题一分析 、机器工作能力分析 根据题中所给信息，每台机器每小时的工作量都不相同，但都在 400 上下左右浮动，下图给出每台机器的各个小时的工作量的均值和方差。 机器工作量均值 机器编号 工作量均值 方差 1 2 3 4 5 6 7 8 12 9 400 10 11 12 18 即在数据波动不是很大的情况下，我们假设机器的工作量均值为机器每小时的工作量， 由于 12 台机器是同一款机器，我们对12 台机器工作量进行均值得到约等于400。为计算方便我们对每台机器的每小时工作量取400。 、时间内需求关系分析 根据题中所给条件，快件在处理是不是实时的，而是一个时间段内的需求必须由另一个时间段内供给。 12：00 以前到达的快件必须在 14：00 以前处理完毕 16：00 以前到达的快件必须在 18：00 以前处理完毕 22：00 以前到达的快件必须在第二天零点以前处理完毕 对于题中时间要求固定几点前满足需求这种非定时性的需求关系，前后几个时间段是相 互影响的，普通方法不易解决。为此，我们引入三个不定时变量 t 描述每个时间段的结束点。为下文叙述方便，在此引入符号定义。 符号定义 符号 说明 Tk1 Tk 2 Tk 3 第 k 天的 12：00 前快件的处理完时间第 k 天的 16：00 前快件的处理完时间第 k 天的 22：00 前快件的处理完时间 时间供求关系示意图 我们对上述时间供需关系进行分析后得到T 的约束关系如下： k1(k ?1) ? 24 ? 12 ? T ? 14 ? (k ?1) ? k1 、机器数量分析 T T ??k1 k 2 ? ? T T k 2 k 3 ? 18 ? (k ?1) ? 24 ? 24 ? (k ?1) ? 24 由于快件数量过多，我们想知道在现有机器数量下能否满足需求。如果不能满足需求我们在下一步对具体需要多少进行求解。 对第一天的第一段需求和第一段供给进行分析，首先第一段需求是从0：00-12：00 总快件数量经过计算后为 63925，第一段供给按照所有机器全部工作并且工作到14：00 满 13 （不能连续工作 8 小时）个小时，即 12*13*400=6240063925 所以现有条件下一定不能满足快件需求。按照以上计算方式，再不考虑前后关系，机器运算时间全满的条件下，我们近似计算了各个时间段最少需要的机器数量。 Table 时间段 快件数量 最少需要的机器数量 0：00-12：00 63925 13 12：00-16：00 21314 14 16：00-22：00 31980 14 22：00-第二天 12：00 74692 15 12：00-16：00 21355 14 16：00-22：00 32365 14 22：00-第三天 12：00 74800 15 12：00-16：00 21537 14 16：00-22：00 32403 14 由以上分析可知在每个时间段工作满的情况下，即不考虑前一个时间段机器连续工作对后一个时间段的影响，所需最少的机器数量在15 个以上，那么我们就为机器数量设置了一个下界 15，在考虑前后时间段的机器连续工作情况下机器数量一定会大于15，对于具体上界而言，就是每个时间段每台机器都要休息一小时。 对此我们根据上表同样的算法求解最多需要的机器数量为 18，则可以通过分析确定总机器数量一定在 15-18 之间。 二、问题一建模 为下文叙述方便，在此我们进行符号定义。 符号定义 符号 说明 N j S i Cij X 第 j 个小时的快件数量第 i 台机器的每小时工作量第 i 台机器是否在j 小时工作 机器总数量 、目标函数的确定 根据题中描述，问题一的目标函数很容易确定，即满足总的使用机器数量最小 minX 、供需约束  （1）T  X ?时间段的供需: ?  Tk1 ?C ?  S ?  24k ?12 ?N ? k1 ij i i?1 j?24k ?24 j j?24k ?24 （2）T 时间段的供需: ?X T?k 2 ? 24?k ?8 k 2 Cij Si k1i?1 j?24k ?24? k1 N j j?24k ?12 （3）T 时间段的供需: ?X T?k 3 ? 24?k ?2 k 3 Cij k 2i?1 j?24k ?24 k 2 Si N j j?24k ?8 、不连续工作约束 ?0，第i台机器不在第j小时工作 ij其中C ? ? ij ?1，第i台机器在第j个小时工作 为叙述方便我们在这里引入Mij 新变量表示第i 台机器在第j 个工时的累计工作时间。 对此我们有如下约束。  Mij ? Cij , j ? 1,i ? 1,2,3,..., K Mij ? Mij?1 ? Cij