摘要
The job-shop scheduling problem with discretely controllable processing times (JSP-DCPT) is a combination of two kinds of sub-problems: the job-shop scheduling problem and the discrete time-cost tradeoff problem. Neither good approximation algorithms nor efficient exact algorithms exist for the bicriteria JSP-DCPT that is to simultaneously minimise the duration and the cost of performing schedules to the problem. An assignment-first decomposition (AFD) and a sequencing-first decomposition (SFD) are proposed for solving the problem. The main difference between the two decompositions lies in the logical sequence for solving the two kinds of sub-problems. The comparison is carried out by evaluating the size of the searching space with respect to each of the two decompositions, and a general conclusion is deduced that for the JSP-DCPT with at least two machines, at least two jobs, and at least two modes for each operation, the efficiency of the searching-based approaches incorporating SFD is superior to that incorporating AFD. Computational studies on JSP-DCPT instances constructed based on a set of well-known JSP benchmarks illustrate the overall superiority of SFD to AFD regarding multiple measure metrics.
源语言 | 英语 |
---|---|
页(从-至) | 7415-7427 |
页数 | 13 |
期刊 | International Journal of Production Research |
卷 | 50 |
期 | 24 |
DOI | |
出版状态 | 已出版 - 15 12月 2012 |