| 摘要(英) |
This study deals with the two-machine flowshop scheduling problem with blocking to minimize total tardiness. The blocking flowshop scheduling problem (BFSP) occurs in a variety production processes where no intermediate buffer exists between machines. In practice, because of the lack of intermediary storage or technical requirements, the feature of blocking should be considered. Such as chemical industry, because there are no buffer storage between machines, a job completed processing on machine 1 has to remain on this machine and to block itself until the next machine is free and available for processing.
In this research, we develop a depth-first search algorithm to find out an optimal sequence. For the dominance criteria, we refer the way of the dominance criteria proposed by Wu (2010), and adopt or modify the proposition which proposed by Kim (1993), Pan, Chen, and Chao (2002), and Schaller (2005) to develop our criteria. For the lower bound, we modify the recursive equations presented in Pinedo (2012) to compute the total tardiness of tardy jobs, and extend the lower bound derived from Schaller (2005) to develop our lower bound. A branch and bound algorithm is built based on the dominance criteria and lower bound, which are implemented in our algorithm to eliminate nodes efficiently in the branching tree.
In the chapter 4, the computation experiences indicate three points. First, we conduct computational analysis to show that the validation and efficiency of our branch and bound algorithm compared with enumeration. The same optimal can be found by enumeration method and our algorithm. The results also show that our algorithm can eliminate more 99% unnecessary nodes. Second, we use four scenarios of Schaller (2005) to test our algorithm. After we compare the performance with the algorithm proposed by Zhong (2013), by the result of T-test (Paired samples test), we find at 95% confidence level, the data provide sufficient evidence to indicate that the dominance criteria and lower bound we proposed have higher effectiveness. When the number of jobs is between 14 and 18, the average number of nodes generated in our algorithm is fewer than the result in Zhong (2013). Moreover, we can increase the solve problem from 18 to 21, and when the parameter of due range T=0.75 and R=0.5, our branch and bound algorithm can derive optimal solution to the instances with up to 25 jobs. Finally, the performance of our algorithm also is analyzed, when the due date is tight and close to nowadays, the number of average processed nodes will decrease, and the optimal can be found in shorter time. |
| 參考文獻 |
[1] Chung, C., J. Flynn and O. Kirca (2002) “A branch and bound algorithm to flow time for m-machine permutation flowshop problems”, International Journal of Production Economics, Vol.79, 185-196.
[2] Chung, C., J. Flynn and O. Kirca (2006) “A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems”, European Journal of Operational Research, Vol. 174, 1-10.
[3] Gong, H., L. Tang and C.W. Duin (2010) “A two-stage flow shop scheduling problem on batching machine and a discrete machine with blocking and shared setup times”, Computers and Operations Research, Vol. 37(5), 960–969.
[4] Grabowski, J. and J. Pempera (2000) “Sequencing of jobs in some production system”, European Journal of Operational Research, Vol. 125 (3), 535–550.
[5] Hall, N.G. and C. Sriskandarajah (1996) “A survey of machine scheduling problems with blocking and no-wait in process”, Operations Research, Vol. 44, 510–525.
[6] Huang, P.X. (2014) “Minimizing Total Tardiness in Flow Shop Scheduling Problem with Blocking”, Unpublished Master’s Thesis, National Center University, Graduate Institute of Industrial Management.
[7] Kim, Y. D. (1993) “A New branch and bound algorithm for minimizing mean tardiness in two-machine flowshops”, Computers & Operation Research, Vol. 20, 391-401.
[8] Lenstra, J.K., A.H.G. Rinnooy Kan and P. Brucker (1977) “Complexity of machine scheduling problems”, Annals of Discrete Mathematics, Vol. 1, 343–362.
[9] Lee, W. C., Y. R. Shiau, S. K. Chen and C.C. Wu (2010) “A two-machine flowshop scheduling problem with deteriorating jobs and blocking”, International Journal of Production Economics, Vol. 124, 188-197.
[10] Pinedo, M. (2012), Scheduling: Theory, Algorithms, and System, Springer, New York.
[11] Pan, J.C.H. and E.T. Fan (1997) “Two-machine flow-shop scheduling to minimize total tardiness”, International Journal of Systems Science, Vol. 28, 405-414.
[12] Pan, J.C.H., J.S. Chen and C.M. Chao (2002) “Minimizing tardiness in a two-machine flow-shop”, Computers & Operation Research, Vol. 29, 869-885.
[13] Reddi, S.S. and C.V. Ramamoorthy (1972) “On the flowshop sequencing problem with no wait in process”, Operational Research Quarterly, Vol. 23, 323–330.
[14] Ronconi, D.P. and V.A. Armentano (2001) “Lower bounding schemes for flowshops with blocking in-process”, Journal of the Operational Research Society, Vol. 52, 1289–1297.
[15] Ronconi, D.P. (2004) “A note on constructive heuristics for the flowshop problem with blocking”, International Journal of Production Economics, Vol. 87, 39–48.
[16] Sen, T. and S.K. Gupta (1984) “A state-of-art survey of static scheduling research involving due date”, Omega, Vol. 12, 63–76.
[17] Schaller. J. (2005) “Note on minimizing total tardiness in a two-machine flowshop”, Computers & Operations Research, Vol. 32, 3273 – 3281.
[18] Sen, T., P. Dileepan and J.N.D. Gupta (1989) “The two-machine flowshop scheduling problem with total tardiness”, Computers & Operation Research, Vol. 16, 333-340.
[19] Zhong, C.R. (2013) “Two-Machine Flow Shop Scheduling Problem with Blocking for Minimizing Total Tardiness”, Unpublished Master’s Thesis, National Center University, Graduate Institute of Industrial Management. |
[Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
至系統瀏覽論文 ( 永不開放)
plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit