摘要
以实际中连续滚动生产为背景，研究了一类新的平行机作业安排问题，即初始状态非平凡的Ｐ∥Ｃ_ｍａｘ问题。基于经典的Ｂｉｎ－ｐａｃｋｉｎｇ（装箱）理论和技巧，提出改进的Ｍｕｌｔｉｆｉｔ算法及相应的ＩＦＦＤ装法，并分析算法在最坏情况下的性能指标上界为４／３．最后，提出连续生产中周期滚动式作业安排的实施算法，实现了设备不空闲而连续运行。
The multifit algorithm for P//Cmax problem is considered in the case that the initial state in task scheduling is not general. The feasibility of the multifit algorithm is analyzed and the worst case performance bound satisfying Rm (MF[k]) ≤4/3 is proved . ln the last, an al- gorithm is also brought forward for realizing the cyclical rolling task scheduling in continuous production, so that the processors consecuctively execute with no idle time .
出处
《烟台大学学报（自然科学与工程版）》
CAS
1998年第3期167-172,共6页
Journal of Yantai University(Natural Science and Engineering Edition)
关键词
平行机调度问题
调度
连续生产
作业安排
装箱
parallel processor scheduling, bin-packing approximation algorithm, worst case analysis, performance bound
