A Two-Stage Flezible Flowshop Problem with Deterioration
We study a scheduling problem under considering deterioration on a two-stage flexible flowshop of particular structure (parallel machines in the first stage and a single batching machine in the second stage). The deterioration of a job means that its processing time on the batching machine is dependent on its waiting time, i.e., the time between the completion of the job in the first stage and the start of the job in the second stage. The objective is to minimize the makespan plus the total penalty cost of batching-machine utilization ratio. First, we prove the problem is strongly NP-hard. An efficient heuristic algorithm for the general problem is constructed and its worst-case bound is analyzed. Computational experiments show that the heuristic algorithm performs well on randomly generated probleM instances.
Hua Gong Lixin Tang
The Logistics Institute, Northeastern University, Shenyang, China
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
651-660
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）