加工时间依赖工件位置的单机成组排序问题

Single-machine with position-dependent processing times of jobs in group technology scheduling

排序问题是一类重要的组合优化问题,现代排序问题突破了经典排序问题的种种假设,有着越来越广阔的应用前景。对加工时间依赖于工件位置的单机成组排序问题进行了研究,讨论了成组技术中,要求同一组内工件必须连续加工,加工时间的函数变量是工件所在的加工位置,目标函数分别为极小化最大完工时间与总完工时间。分别给出其多项式时间的最优算法。

Scheduling is an important combinatorial optimization problem. The modern scheduling problems that break through the various assumptions of the classical ones hold out more and more broad prospects. Several recent papers focused on the jobs with position - dependent processing times on the optional solution of schedu- ling problems. In this paper the jobs are classed into groups and the jobs in the same group must be processed in succession, each group requires an independent setup time. Makspan and total completion time is the criteria. The algorithm for the two cases are presented.