带单服务器和相同加工时间的流水作业排序问题

Scheduling a Single Server and Equal Processing Times in a Two-machine Flow-shop

研究带单服务器和相同加工时间的两台机器的流水作业排序问题,证明该问题是强NP-困难的,引入一个简单的贪婪算法证明其紧界是3/2.

We consider the problem of two-machine flow-shop scheduling with a single server and equal processing times,we show that this problem is NP-hard in the strong sense and present a simple greedy algorithm for it with worst-case bound 3/2.