一致性条件下带磨损因子的排序问题

Scheduling Problem with Wearing Effect under Consistent Condition

考虑下述带磨损因子的排序问题:n个工件需在同台机器上依次加工,工件j,j=1,2,…,n,所需的加工时间同它被开始加工的时间有关,当工件j开始被加工的时间为t时其所需的加工时间为p=btjj, 其中bj可视作与工件j有关的一个磨损因子.要求适当排列这n个工件的加工顺序,使某目标函数值达最小.对最大迟后、最大延误、加权完工时间之和这三个目标函数,文中给出了相应条件下的最优算法.

This paper discusses the following scheduling problem with wearing effect: n jobs need to be processed on the same machine, the processing time for job j , j=1,2,...,n, is affected by its starting time of processed, the later, the more. Namely, if the starting processing time for job j is t, then the processing time it needed is pj=bjt, in which bj can be seen as a wearing effect connected with job j. We are asked to sequence the n jobs in such a way that some objective functions are minimized. For the following three objective functions which are the makespan, the total completion time and the maximum lateness, the sum of weighted completion times, this paper constructs the optimal sequence under corresponding conditions respectively.