钢铁企业生产与运输费用协调调度问题

Coordinated Machine Scheduling and Conveyance Problems of a Steel Works

针对钢铁企业生产前存在不可忽略运输的实际,研究了生产与生产前运输费用协调调度问题.由于钢铁企业被调度的工件体积较大及加工前不能等待太长的时间,因此运输车辆的容量及工件在机器前的缓冲等待时间有限制.考虑的机器环境为单机环境,单机前有无限的缓冲空间,运输车辆数目无限,调度的目标函数为传统的调度函数加上运输费用.对于不同的目标函数,证明了工件在单机加工前缓冲等待时间有限制的调度问题是强NP难的,对于运输车辆有容量限制问题的可解情况给出了多项式时间算法.

The objective to study on is to minimize the overall cost of both production and in-situ conveyance that should not be ignored in the supply chain scheduling of a steel works. Limited capacity of transporters and limited waiting time of jobs before their processing should be taken into account. To simplify the problem, it is assumed that the machine to use is just a single machine on which the job to be processed has limited time to await with unlimited number of transporters ready for use. Thus, the objective function for scheduling becomes the conventional scheduling function plus conveyance cost. For different objective function, the problem of scheduling is proved strongly NP-hard if a job has limited waiting time before processed on a single machine. As to the solvable case that the capacity of transporters is limited, some polynomial time algorithms are given.