一类快件处理问题的研究

席晋聪

(太原科技大学,山西 太原030024)

1 概述

物流公司只有把商品快速、准确、低成本送到消费者手中,赢得消费者的好评,才能延续与商家的合作,因此一个高效经济的物流公司是商家的首选合作伙伴。

本文是对某一中转中心的数据进行整合分析,合理处理机器的休息时间,结合实际情况构造的线性优化模型运用C++语言进行编程求解,求解得出不考虑加急快件的情况下,基本满足供给的机器数量。

本文用到的是某物流公司的其中一个中转中心记录某四天的每隔1 分钟到达的快件数量,约4320 个数据以及其它情况:处理快件的机器数量12 台,该12 台机器同时开工同时休息,每台机器连续运转时间不能超过8 小时,超过8 小时后需要关机休息1 小时才能继续工作。

目前一般的快件处理要求是:

(1)12:00 以前到达的快件必须在14:00 以前处理完毕。

(2)16:00 以前到达的快件必须在18:00 以前处理完毕。

(3) 22:00 以前到达的快件必须在第二天零点以前处理完毕。

该中转中心出现的问题:经常因为很多快件发送不及时而遭到总部的批评,因此至少需要多少台现有设备,才能基本满足要求。

2 问题分析

针对这一问题,我们首先对记录的数据进行整合分析,对数据进行了预处理,确定出机器工作的闲期及忙期。按照要求构造目标函数,再按照快件处理要求的时间节点建立约束条件进行线性优化,求解得出最优化结果。

3 模型假设

3.1 假设题目中的数据不具有偶然性。

3.2 假设没有节假日,活动等可能导致快件突增或突减的因素。

3.3 机器无故障等突发因素。

4 模型的建立与求解

模型的建立:

思路:本文首先假设输入的总设备1 为X 台,从13 台开始算起,(即x＝13)之后每次加1 进行循环,直至符合题意输出要求的X 为止。本文将两天作为一个循环,每天分为三个阶段(第一阶段为22:00-12:00,第二阶段为12:00-16:00,第三阶段为16:00-22:00),这三个阶段恰好为一天,但由于第一天第三阶段可能会处理第二天第一阶段的快件,本文建立的线性优化模型是以两天作为一个循环单位的。

首先进行第一阶段的检验,判断总设备1 的台球* 设备1的工作速度* 第一天第一阶段的工作时间(即0:00 到14:00,中间机器会休息1 小时)是否大于等于第一阶段到达的快件数,(即22:00 到12:00)如果不成立则返回第一步,带入X+1重进进行计算,直至满足上述条件为止,当满足上述条件后,进行进一步的检验,验证第一阶段的处理余量(这里指处理完本阶段快件到达数,还剩余的工作效率)是否大于等于每阶段快件处理的时间差两小时(即12:00 到14:00)到达的快件数,不论是否成立都进行下一步的判断,只是下一阶段需要处理的快件数量不同。

上式成立的前提下,判断总设备1* 工作速度* 第一天第二阶段的工作时间(即14:00 到18:00)是否大于等于第二阶段到达的快件数和之前已经处理了2 小时快件的差(即14:00 到16:00 到达的快件),(说明:这里之所以不能用这一阶段快件到达数减上一阶段的加工余量进行判断,是因为快件处理时间差只有两小时,如果这一阶段加工余量过大,也只能解决之后两小时的快件,导致设备效率不高)如果不成立,则返回第一步,带入X+1 重新计算,直至满足该条件为止,成立之后。则进行进一步的验证。验证本阶段的加工余量是否大于等于本阶段快件处理时间差两小时到达的快件数(即14:00 到18:00 到达的快件),不论是否成立,均进行下一步的判断。

上式如果不成立,则需要判断总设备1* 工作速度* 第一天第二阶段的工作时间(即14:00 到18:00)是否大于等于本阶段到达的快件数减上一阶段的加工余量。如果不成立返回第一步,带入X+1 重新计算,直至满足条件为止,满足条件后则进行进一步的判断。判断本阶段的加工余量是否大于等于本阶段的快件处理时间差两小时到达的快件数。不论是否成立,均进行下一阶段的判断。

同理进行第三阶段的判断,以后进行更多的约束,直至列出题目中所有的约束条件。

(目标函数) Zmin＝x1

(约束条件)v1* ti0* x1≥pi0- m——1

判断x1台设备1 能否在0:00 到14:00 解决22:00 到12:00 的快件(m 是前一天解决的22:00 到23:00 的快件数)

v1* ti0* x1- pi0+ m ≥ki00+ ki01——2

判断x1台设备1 能否在0:00 到14:00 解决12:00 到14:00 的快件

若2 成立ti1* v1* x1≥pi1- ki00- ki01——3

判断x1台设备1 能否在14:00 到18:00 解决14:00 到16:00 的快件

若2 不成立v1* ti0* x1- pi0+ m + ti1* v1* x1≥pi1——4

判断x1台设备1 能否在14:00 到18:00 解决16:00 到17:00 的快件

若3 成立ti1* v1* x1- pi1+ ki00+ ki01≥ki10——5

判断x1台设备1 能否在14:00 到18:00 解决16:00 到17:00 的快件

若4 成立 v1* ti0* x1- pi0+ m + ti1* v1* x1- pi1≥ki10——6

判断x1台设备1 能否在12:00 到18:00 解决16:00 到17:00 的快件

若5 成立ti2* v1* x1≥pi2- ki10——7

判断x1台设备1 能否在18:00 到24:00 解决17:00 到22:00 的快件

若5 不成立ti*v1* x1- pi1+ ki00+ ki01+ ti2*v1* x1≥pi2——8

判断x1台设备1 能否在16:00 到24:00 解决16:00 到22:00 的快件(前半部分是16:00 到18:00 处理的部分16:00到18:00 的快件)

若6 成立ti2* v1* x1≥pi2- ki10——9

判断x1台原机能否在18:00 到24:00 解决17:00 到22:00 的快件

若6 不成立v1* ti0* x1- pi0+m+ti1*v1*x1-pi1+ti2* v1*x1≥pi2——10

判断x1台设备1 能否在16:00 到24:00 解决16:00 到22:00 的快件(前半部分是16:00 到18:00 处理的部分16:00到18:00 的快件)

若7 成立ti2* v1* x1- pi2+ ki10≥ki20——11

判断x1台设备1 能否在18:00 到24:00 解决22:00 到23:00 的快件

若11 成立,m = ki20n = 1

若11 不成立,m =ti2* v1* x1- pi2+ ki10n = 1

若8 成立；ti1* v1* x1- pi1+ ki00+ ki01+ ti2* v1* x1-pi2≥ki20——12

判断x1台原机能否在16:00 到24:00 解决22:00 到23:00 的快件

若12 成立,m = ki20n = 1

若12 不成立m = ti1* v1*x1-pi1+ ki00+ ki01+ ti2* v1*x1-pi2n=1

若9 成立ti2* v1* x1- pi2+ ki10≥ki20——13

判断x1台原机能否在18:00 到24:00 解决22:00 到23:00 的快件

若13 成立m = ki20n = 1

若13 不成立,m =ti2* v1* x1- pi2+ ki10n = 1

若10 成立v1* ti0* x1- pi0+m+ti1* v1* x1- pi1+ ti2* v1* x1- pi2≥ki20——14

判断x1台原机能否在16:00 到24:00 解决22:00 到23:00 的快件

若14 成立,m = ki20n = 1

若14 不成立,m = v1* ti0* x1- pi0+ m + ti1* v1* x1-pi1+ ti2*v1*x1- pi2n =1

每天0 点n 会重置为0,能准时处理完三天的快件则n=1。如果在到第二天前没准时处理完快件,退出循环,x1+1 后再次进入循环,当有一个x1符合条件时,退出所有循环,输出x1。

将预处理数据带入上述模型,通过C++语言编程求解得出Zmin＝x1＝15,

问题结论:

综上所述,按照本文所述模五,在不考虑加急快件的情况下,至少需要15 台现有设备,才能基本满足该中转中心的要求。

5 模型的改进与推广

模型的改进:因为在建模时,约束条件是根据该中转中心的要求进行建立,所以不同的要求需要建立不同的约束条件,使得该模型在解决实际问题时受到限制。

模型的推广: 该模型可以解决现实生活中的病床安排、银行排队、售票处售票、工厂维修人员安排等许多问题,可以对合理利用资源起到很好的模拟作用,具有很强的现实意义。