科研之友
微信
新浪微博
Facebook
分享链接
摘要
This paper considers a cutting and scheduling problem of minimizing scrap motivated by float glass manufacturing and introduces the float glass scheduling problem. We relate it to classical problems in the scheduling literature such as no-wait hybrid flow shops and cyclic scheduling. We show that the problem is NP-hard, and identify when each of the problem's components are polynomially solvable and when they induce hardness. In addition, we propose a simple heuristic algorithm, provide its worst-case performance bounds, and demonstrate that the bounds are tight. When the number of machines is two, the worst-case performance is 5/3.
- 出版日期2014-2
