| 摘要(英) |
In this research, we consider the problem of scheduling n jobs on hybrid flow shop with job splitting property, and our objective is to minimize the maximum completion time. In the past, the majority of scheduling studies assumed that each job can be processed on at most one machine at a time. In the real word, there are many cases that have different types of products and each type of products have numbers of units need to go through a production line. In order to make these products finished as soon as possible, it is normal to schedule each unit of the same product on different machines at the same time.
In this research, we assume that there are two identical parallel machines in the first stage and a single machine in second stage, and the setup time of each job are independent. We use a branch and bound algorithm to find the optimal solution for this problem. In this algorithm, we propose the lower bound and upper bound for this scheduling problem and we use some dominance rules to eliminate unnecessary nodes to improve the efficiency of our algorithm. Finally, we implement this algorithm by JAVA, and we conduct the computational analysis.
|
| 參考文獻 |
[1] Fattahi, P. et al. (2013), “A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations”, Applied Mathematical Modelling , Vol. 38, pp. 119–134
[2] Brah, Shaukat A. et al. (1991) ”Branch and bound algorithm for the flowshop with multiple processors”, European Journal of Operation Research, Vol.51, pp. 88- 99.
[3] Portmann, M.C. et al. (1997) ”Branch and bound crossed with GA to solve hybrid fowshops”, European Journal of Operation Research, Vol. 107, pp.389-400.
[4] Allaoui, H. et al. (2004) ”Integrating simulation and optimization to schedule a hybrid flowshop with maintenance constraints”, Computers & Industrial Engineering, Vol. 47, pp.431– 450.
[5] Kim, Y.D. et al. (2004) ”Parallel machine scheduling considering a job-splitting property” , International Journal of Production Research, Vol. 42, pp.4531– 4546.
[6] Kis, Tamás et al. (2005) “A review of exact solution methods for the non-preemptive multiprocessor flowshop problem”, European Journal of Operation Research, Vol.164, pp.592-608.
[7] Xing Wenxun et al. (2000) “Parallel machine scheduling with splitting jobs”, Discrete Applied Mathematics, Vol.103, pp.259-269.
[8] Shim Sang-Oh et al. (2008) “A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property”, Computers & Operations Research, Vol. 35, pp.863 - 875
[9] Ruiz Ruben et al. (2010) “The hybrid flow shop scheduling problem”, European Journal of Operational Research, Vol.205, pp.1–18
[10] Rajendran, C. et al. (1992) ”Scheduling in n-job, m-stage floswhop with parallel processors to minimize makespan”, International Journal of Production Economics, Vol.27, pp.137–143.
[11] Gupta, J.N.D. et al. (1997) “Scheduling a two-stage hybrid flow shop with parallel machines at the first stage”, Annals of Operation Research, Vol.69 pp.171-191
[12] Gupta, J.N.D. et al. (1988) ”Two-stage hybrid flow shop scheduling problem”, Journal of the Operational Research Society Vol. 39, pp.359-364.
[13] Potts, C.N. et al. (1992) “Integrating scheduling with batching and lotsizing: a review of algorithm and complexity”, The Journal of the Operational Research Society Vol. 43(5), pp.395-406.
[14] Xing, W. et al. (1998) “Splitting parallel machine scheduling (in Chinese)”, Operation. Research Transactions”, Vol. 2, pp.30-41.
[15] Hoogeveen, J.A. et al. (1996) “Preemptive scheduling in a two-stage multiprocessors flow shop is NP-hard”, European Journal of Operational Research, Vol.89(1), pp.172-175.
[16 ] Haouari Mohamed et al. (2006) “Optimal Scheduling of a Two-Stage Hybrid Flow Shop”, Mathematical Methods of Operations Research, Volume 64, pp 107-124.
|
[Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
至系統瀏覽論文 ( 永不開放)
plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit