流水作业由二台柔性机器组成时的极小完工时间之和问题

Minimizing Total Completion Time of Jobs on a Flexible Two Machine Flow Shop

该文考虑下述由2台机器组成的流水作业问题:n个相同工件需依相同次序在机器1、2上共进行3次加工.工件j的第一次加工在机器1上进行,所需时间为p1;其第二次加工或单独在机器1上或单独在机器2上进行,当工件j的第二次加工在机器1上进行时,所需时间为p12,当工件j的第二次加工在机器2上进行时,所需时间为p21;其第三次加工需在机器2上进行,所需时间为p2.要求适当安排这n个工件的加工方式以使它们的完工时间之和达到极小.对该问题作者对应不同情况给出了不同的最优解法.

This paper considers the following scheduling problem on a flow shop composed of two flexible machines: N identical jobs must be processed in the same sequence through a two-machine flow shop. Each job must be processed for a total of three times on both machines. The job is first processed on machine 1 with a processing time p_1. It is then processed on machine 1 or 2 for the second time. If it is processed on machine 1, the processing time is p_(12), while the processing time is p_(21) if processed on machine 2. Finally, the job is processed for the third time on machine 2 with a processing time p_2. A proper sequence of processing is sought such that the total processing time of n jobs is minimized. For such a scheduling problem, different optimal algorithms are constructed corresponding to different cases.