Scheduling a Two-machine Flowshop Problem with a Single Server
This paper investigates scheduling a two-machine flowshop problem with a single sever to minimize makespan. The problem under our consideration generalizes the problem that the server only performs setup operation. The server in our problem needs an additional removal operation for each job. We first show that the problem is strongly NP-haril. An optimal solution property which can be also regarded as a lower bound is then proposed. Based on the property, we construct two heuristic algorithms for the problem. The worst-case performance of the heuristics is analyzed and the average performance of the heuristics is computationally evaluated. The results show that the proposed heuristics are capable of generating near-optimal solutions.
scheduling single server strongly NP-hard worst case analysis heuristics
Xie Xie Yanping Li
Key Laboratory of Manufacturing Industrial and Integrated Automation, Shenyang University, Shenyang Liaoning, 110044, China
国际会议
昆明、丽江
英文
362-365
2011-04-15（万方平台首次上网日期，不代表论文的发表时间）