CAJ | 학술논문

为了研究更具实际意义的带有位置依赖影响的分组调度决策问题,建立了一般性位置依赖的分组调度模型.在模型中,分组实际发动时间和工件的实际加工时间被表示成初始时间和调度位置的一般函数.此类函数没有被假设为特殊函数形式,且没有要求限制其函数单调性.通过数理逻辑分析和证明,把所研究的问题模型分解为组调度过程和工件调度过程,并把每个调度过程分别转化为经典任务分派问题和单机排序调度问题,进而分析问题求解的计算复杂度.研究表明,即使在一般性位置依赖的模型假设下,单机最小化时间表长的分组调度问题和平行机最小化总负荷的分组调度问题仍然是多项式可解的.
위료연구경구실제의의적대유위치의뢰영향적분조조도결책문제,건립료일반성위치의뢰적분조조도모형.재모형중,분조실제발동시간화공건적실제가공시간피표시성초시시간화조도위치적일반함수.차류함수몰유피가설위특수함수형식,차몰유요구한제기함수단조성.통과수리라집분석화증명,파소연구적문제모형분해위조조도과정화공건조도과정,병파매개조도과정분별전화위경전임무분파문제화단궤배서조도문제,진이분석문제구해적계산복잡도.연구표명,즉사재일반성위치의뢰적모형가설하,단궤최소화시간표장적분조조도문제화평행궤최소화총부하적분조조도문제잉연시다항식가해적.
In　order　to　investigate　more　realistic　group scheduling problems with position-dependent effects, the model of general position-dependent group scheduling is proposed,where the actual group setup times and actual processing times are described by general functions of the normal group setup time and position in the sequence.These general functions are not assumed to have specific function structures, and are not restricted to be monotone. By mathematical analysis and proof,each considered problem is decomposed into a group scheduling process and a job scheduling process,and each scheduling process is transferred into the classic assignment problem or the classic single-machine sequence problem, and then the computational complexity to solve the considered problem is analyzed.Analysis results show that, even with general position-dependent job processing times, both the single machine makespan minimization group scheduling problems and the parallel-machine total load minimization group scheduling problems remain polynomially solvable.