臺灣博碩士論文加值系統

本研究探討雙機台流程式生產環境下具批量與等候時間限制和幾台架設時間的多產品排程問題。本研究使用的方法是用批量的方式來減少完工時間，並且使用分支界線法來計算。此篇探討2機台和n個產品，每個產品都有不同的架設時、工作時間和等候時間的限制。每一個產品要進入到幾台1的時候，都會先有架設時間，接著要考量此產品的等候時間限制，要在等候時間內到機台2工作，最後的到完工時間。在批量生產的情況下完工時間會縮短，因此探討批量生產來減少完工時間。等候時間限制的情況是每個產品都有的屬性範圍，實際的等候時間不能超過產品等候時間最大上限。
本文建構一個分枝界線演算法來求得最佳的完工時間，並且分析此分枝界線演算法的成效，使用四種特性和上下限來使分支界線法的效率更佳化，最後分析分支界線法的成效和數據的分析。

The purpose of this study is to treat the optimal lot streaming for multiple products in two-machine flow shops with limited waiting time constraint and setup time for multiple products. In this study, we will introduce about lot streaming and calculate the optimal size. We also use the branch and bound algorithm to obtain the optimal solution. Our objective is to minimize the makespan in lot streaming manufacturing system. Lot streaming is the method that can produce sublots to reduce the makespan and operations can be overlapped. Besides the lot streaming, we also consider about some constraints. We consider limited waiting time and setup time in different products. Limited waiting time constraint is that the products must be transferred to next the machine in the specific time range. Additionally, the limited waiting time constraint is that the waiting time cannot be greater than the upper waiting time. There is setup time in different machines when different products are processed on different machines. At last, we will construct the branch-and-bound algorithm and use the bounding to eliminate nodes efficiently.
According to four properties, upper bound and lower bound the efficiency of the algorithm can be promoted. After constructing the branch-and-bound algorithm, we will analyze the performance of the algorithm and data.

Content..................................................................i
List of figures.........................................................iii
List of tables..........................................................iv
Chapter 1 Introduction...........................................1
1.1 Motivation and background..............................1
1.2 Problem description.........................................2
1.3 Research objectives.........................................3
1.4 Research methodology.................................... 4
Chapter 2 Literature review....................................5
2.1 Makespan minimization with lot streaming in two-machine flow shops..............................................................5
2.1.1 Lot streaming problem with integer-sized sublots in two-machine flow shops................................................5
2.1.2 Lot streaming problem with continuous-sized sublots in two-machine flow shops.........................................6
2.2 Lot-streaming with setup time...........................7
2.3 The scheduling with limited waiting time constraint.........7
Chapter 3 Lot streaming for multiple products in two-machine flow shops with limited waiting time constraint and setup time..........................................................................9
3.0 Notation and problem assumptions....................10
3.1 Linear programming for lot streaming.................11
3.1.1 The sublot size..................................................12
3.2 Lot streaming with limited waiting time constraint..........13
3.3 Lot streaming for multiple products.....................14
3.4 Branching out the nodes .....................................17
3.5.1 Calculating the upper bound by revising Johnson’s rule.............................................................................20
3.5.2 Calculating the lower bound..............................20
3.6 Branch and bound algorithm.................................21
Chapter 4 Computational Analysis..............................24
4.1 Validation of the algorithm...................................24
4.2 Generation of data and examples.........................27
4.3 Performance of algorithm......................................29
Chapter 5 Conclusion..................................................35
5.1 Research contribution............................................35
5.2 Research limitation................................................36
5.3 Further research....................................................36
Reference.....................................................................37
Appendix.....................................................................39

[1] Alfieri, A., Glass, C. and Velde, S. (2012), “Two-machine lot streaming with
attached setup times”, IIE Transactions, 44(8), 695-710.
[2] Baker, K.R. (1995), “Lot streaming in two-machine flow shop with setup times”,
Annals of Operations Research, 57(1), 1-11.
[3] Chang, J.H. and Chiu, H.N. (2005), “A comprehensive review of lot streaming”,
International Journal of Production Research, 43(8), 1515-1536.
[4] Chen, J. and Steiner, G. (1999), “Discrete lot streaming in two-machine flow
shops”, Infor, 37, 160-173.
[5] Chen, J. and Steiner, G. (2003), “On discrete lot streaming in no-wait flow shops”,
IIE Transactions, 35, 91-101.
[6] Chen, J. and Steiner, G. (1997), “Approximation methods for discrete lot
streaming in flow shops”, Operations Research Letters, 21(3), 139-145.
[7] Chen, G. and Steiner, G. (1996), “Lot streaming with detached setups in three-
machine flow shops”, European Journal of Operational Research, 96,591-611.
[8] Chen, X.M (2003), “Lot streaming and scheduling of multiple products in two-
machine flow shops with limited waiting time constraint”, National Central University Industrial Engineering and management, Master’s thesis.
[9] Cheng, M., Mukherjee, N.J. and Sarin, S.C. (2013), “A review of lot streaming”,
International Journal of Production Research, 51(23-24), 7023-7046.
[10] Feldmann, M. and Biskup, D. (2008), “Lot streaming in a multiple product
permutation flow shop with intermingling”, International Journal of Production
Research, 46(1), 197-216.


[11] Glass, C. and Possani, E. (2011), “Lot streaming multiple jobs in a flow shop”,
International Journal of Production Research, 49(9), 2669-2681.
[12] Joo, B.J. and Kim, Y.D. (2009), “A branch-and-bound algorithm for a two-
machine flowshop scheduling problem with limited waiting time constraints”,
The Journal of the Operational Research Society, 60(4), 572-582.
[13] Kumar, S., Baghci, T.P. and Skriskandarajah, C. (2000), “Lot streaming
scheduling heuristics for m-machine no-wait flowshops”, Computer & Industrial
Engineering, 38, 149-172.
[14] Pan, Q. K. and Ruiz, Ruben (2012), “An estimation of distribution algorithm for
lot-streaming flow shop problems with setup times”, Omega, 40, 166-180.
[15] Potts, C.N. and Baker, K.R. (1989), “Flowshop scheduling with lot streaming”,
Operations Research Letters, 8, 297-303.
[16] Sriskandarajah, C. and Wagneur, E. (1999), “Lot streaming and
scheduling multiple products in two-machine no-wait flowshops”, IIE
Transactions, 31(8), 695-707.
[17] Trietsch, D. and Baker, K.R. (1993), “Basic techniques for lot streaming”,
Operations research, 41(6), 1065-1076.
[18] Ullrich, C.A. (2013), “Integrated machine scheduling and vehicle routing with
time windows”, European Journal of Operation Research, 227, 152-165.
[19] Vickson, R.G. (1995), “Optimal lot streaming for multiple products in a two-
machine flow shop “, European Journal of Operation Research, 85, 556-575.
[20] Yang, D.L. and Chern, M.S. (1995), “A two-machine flowshop sequencing
problem with limited waiting time constraints”, Pergamon, 28(1), 63-70.