具有时间与位置相关的两类平行机排序问题

研究带有维修时间限制的时间和位置效应平行机排序问题，涉及同型机和非同类机两种机器类型.工件的实际加工时间同时受到位置效应和时间效应影响，且机器具有维修限制.目标函数由机器负载，总完工时间与总等待时间组成.非同类机情形下，通过将排序问题转化为指派问题，给出多项式时间算法，其算法的时间复杂度为O（n^k+2/（k-1）!）.同型机情形下通过转化目标函数，使用匹配算法得出排序问题的多项式时间解，其时间复杂度为O（（2n+m+n log n）n^k-1/（k-1）!）.

Scheduling problem with time-and-position-dependent effect on two parallel machines environments

This paper studies parallel-machine scheduling problems with time-andposition effect and maintenance restrictions, which parallel-machine environments are only involved with the identical parallel machines and unrelated machines. The actual processing time of the job is the function of position and time, and machines need to be maintained. Objective function is consisted of total machine load, total completion time and total waiting time. Under unrelated machines, the proposed problem can be solved by transferring into assignment problem, which its time complexity is O(n^k+2/(k-1)!). Under identical parallel machines, the proposed problem can be solved by matching algorithm, which its time complexity is O((2n+m+n log n)n^k-1/(k-1)!).