CAJ | 학술논문

讨论了一类两台机流水作业要求最后完工工件完工时间最早的排序问题.问题中每个工件包含两个加工任务:第1个任务可以在任何一台机器上加工,第2个任务只能在第1个任务完成后在第2台机器上加工.如果要求在加工同一个工件的两个任务时,两个任务之间不能有停顿,则称其为不可等待的模型,记作NSHFS.如果第2个任务可以在第1个任务完成后的任意时间加工,则称其为允许等待的模型,记作SHFS.对于SHFS模型,在魏麒和何勇工作的基础上给出了一种改进的最坏情况界为8/5的多项式时间近似算法.对于NSHFS模型,首先证明它是NP-难的,并且给出了一种最坏情况界为5/3的多项式时间近似算法.
토론료일류량태궤류수작업요구최후완공공건완공시간최조적배서문제.문제중매개공건포함량개가공임무:제1개임무가이재임하일태궤기상가공,제2개임무지능재제1개임무완성후재제2태궤기상가공.여과요구재가공동일개공건적량개임무시,량개임무지간불능유정돈,칙칭기위불가등대적모형,기작NSHFS.여과제2개임무가이재제1개임무완성후적임의시간가공,칙칭기위윤허등대적모형,기작SHFS.대우SHFS모형,재위기화하용공작적기출상급출료일충개진적최배정황계위8/5적다항식시간근사산법.대우NSHFS모형,수선증명타시NP-난적,병차급출료일충최배정황계위5/3적다항식시간근사산법.
This paper investigates a variant scheduling problem of minimizing makespan in a two-machine flow shop.In this variant,there will be two tasks for each job.The first task can be processed on either machine,and the second task can only be processed on the second machine after the first task has been finished.Furthermore,if the second task should start right after the first task is completed,it is called a no-waited case and is denoted by NSHFS.On the other hand,if the second task is allowed to be processed at any time after the first task is completed,the problem is then denoted as SHFS.In the case of SHFS,based on the result of Wei and He,an improved polynomial time approximation algorithm with worst-case ratio of 8/5 is presented.In the case of NSHFS,this paper shows that it is NP-hard,and presents a polynomial time approximation algorithm with worst-case ratio of 5/3.