有调整时间的两机器流水作业总流程问题

MINIMIZING TOTAL COMPLETION TIME IN TWO-MACHINE FLOW PROCESS WITH SETUP TIME ADJUSTING

在两机器流水作业问题中 ,每个工件在加工前有一调整时间 ,同一工件的调整是可以重叠的 ,但加工时间不能重叠 .本文以总流程为最优准则研究调整时间独立于加工时间的两机器流水作业问题 ,给出了问题最优解中工件排序应满足的条件 ;其次讨论当工件的两种时间满足一定条件时最优时间表的求法 ;

For two-machine flow process problem, each job has a setup-time before it is processed, the setup step of the same job can be overlapped on two-machine, but the processing step can't. In this paper, the author give the conditions satisfied by sequence in solution of total completion problem for two-machine flow process problem with setup and processing time separated. When these two times satisfy some condition, the above problem can be solvable in polynomial time. Finally, some approximation algorithms are constructed.