带服务器的3台机器流水作业排序启发式算法

研究了带服务器的流水作业排序问题的复杂性和启发式算法.每个工件在机器上加工之前,必须由服务器先进行安装,在任何时刻服务器只能在1台机器上安装工件,目标是使最大加工时间达到最小.在只有3台机器的情况下,利用3-划分到该问题的一个归约来证明该流水作业排序问题仍然是强-困难的.为此,引入一个新的启发式算法,并证明该启发式算法的紧界为2.

Heuristic algorithm for three-machine flow-shop problem with a single server

The complexity and heuristic algorithm for the flow-shop scheduling problem with a single server,are studied.Setup times are considered first if a job must be loaded on a machine. We assume that all setup times have to be done by a single server, which can handle at most one job at a time. The objective is to determine a feasible schedule, which minimizes the makespan. Through a reduction from the 3-partition problem to the three-machine flow-shop scheduling problem with a single server, we can proof this problem is NP-hard in the strong sense, too. For a new heuristic algorithm, the worst-case performance is 2; and the bound is tight.