急啊-纸箱厂的调度算法

liyanping998

某纸箱厂日常生产各种纸箱，由于该厂只和少数客户有长期协作关系，如：电视机厂、洗衣机厂、摩托车厂、电焊条厂、洗衣粉厂、邮局等，在比较长的时间内他们的纸箱大小都保持不变, 每月的订货数量也基本相同。除此之外都是顾客临时电话或上门来订货，故而顾客的到达、顾客的订货数量、所订纸箱任务的要求和尺寸都具有比较大的随机性，尤其纸箱大小几乎全不相同。而且纸箱的颜色有白色和土黄色的两种，纸张的质量也有好、中、差三种（本题中暂不考虑），纸板的型号也有两种（主要是瓦楞的弯曲程度不同、因而所能够承受力的大小也不同，1型优于2型，当然价格也是1型比2型贵15%。当然纸箱四壁中瓦楞的方向更不可改变，否则无法承受来自上方的压力，详细见下面纸板的长、宽的计算方法），至于交货日期也早晚不等，最迟的可能15天交货也行，最早的会要求后天下班前交货（这种情况下可适当提高纸箱的单价）。由于订货情况的特殊性，该厂非常重视产品质量（原料质量和型号不能降低，但可以提高）和交货时间方面的信誉。
目前该厂每天大约有20批左右的任务，任务总和一般占到其最大生产能力的80%左右，而且如果任务紧急，可以通过加班来完成。该厂每天的生产任务由厂调度员在前一天下班前下达，一般不再更改。由于制造纸箱的纸板在流水线上生产，而在流水线上作为原料用的大型纸卷的宽度只有1.2米,1.3米,1.6米,2.2米四种规格(长度可认为足够长),所以每次仅生产一种纸箱所需要的纸板几乎总造成比较大的浪费,为此应该将不同尺寸的纸箱搭配在一起生产以减少浪费。如果进行搭配生产，因为受到流水线设备的限制，只能按调度员所选择的宽度的纸卷来生产纸板，刚制造完的纸板立即在同一条流水线上被切成两种不同规格的纸板，并且这两种不同规格的纸板最多只能有一种可以再切成相同的两块（因为流水线上最多只能够让三把纵向刀和两把横向刀同时工作，如图1）。过去该厂一直由调度人员根据自己的经验来安排生产,即使最有经验的调度员仍然会有一些可以避免的浪费,为进一步降低成本,该厂打算利用计算机寻找浪费更小的调度方案,特聘请你们为他们制定算法。
附：纸箱的大小（长、宽、高）与所需要纸板的大小（长、宽）的关系是（见图2）：
" N5 C- P" `' ?; L  m% {纸板长=（纸箱长+纸箱宽）的两倍再加上5厘米（接头部分），由于纸箱主要受到来自上方的压力，故流水线上纸的方向和纸板长的方向一致。
: k0 A8 ]2 R! p6 W纸板宽=纸箱高+纸箱宽（纸箱宽度的两个1/2分别用于作纸箱上、下底面）
# A% D1 g0 X. Z/ j* @) o; T" O* b   注：太小的纸箱不安排在流水线上生产，因而在每天20批左右的生产任务中完全可以不考虑纸板顶面积小于等于900平方厘米的纸箱。
; @2 u4 `) P2 a. c1 ?2 B- k; N! N# Y7 l数据在附件里~~~

liyanping998

第一次搞这个东西，没思路啊~

ljwabc115

来一个悬赏解题吧,这题目工程量很大诶

liyanping998

只是给点思路和想法就可以了