A note on the algorithm LPT-FF for a flowshop scheduling with two batch-processing machines

作者：Dong, Jianming; Hu, Jueliang; Lin, Guohui^*

来源：Optimization Letters, 2016, 10(1): 109-118.

DOI：10.1007/s11590-015-0859-6

• Flowshop scheduling
• Batch-processing machine
• Bin-packing
• Approximation algorithm
• Worst-case performance analysis

A flowshop scheduling problem with two batch-processing machines is investigated in this paper, with the optimization goal to minimize the makespan. When the job processing times on the two machines are positively correlated, a -approximation algorithm for this NP-hard problem was previously proposed. We show that this algorithm has a worst-case performance guarantee of .

• 出版日期2016-1
• 单位浙江理工大学