臺灣博碩士論文加值系統

零工式生產系統 (job-shop production system)為常見之生產系統，大多配置有多種類型的機器在工作站(workstation)內以提高生產彈性。該生產系統之工作站內能正常運轉之機器數會因為其失效、維修或者停機等各種因素而呈現隨機之多階狀態，因此零工式生產系統可被視為多階狀態網路 (multistate network)。從生產管理之觀點，網路可靠度 (network reliability) 可作為評估一個製造系統之重要績效指標，因此多數管理者以找出具有最大化網路可靠度同時最小化成本的機器配置作為目標，此即為一多目標最佳化問題。本研究即以零工式生產網路的多目標最佳化為主軸，分為兩部分進行以下求解。第一部分：為了計算零工式生產系統之網路可靠度，本研究導入網路拓樸的概念，建構多階狀態零工式生產網路 (multistate job-shop production network)。有別傳統製造網路，零工式生產中一個工作站將配置有多種類型之多台機器，故工作站內能正常使用之機器數量並不具有明確的狀態分布，且隨著機器種類增加，將增加網路可靠度計算之難度。因此本研究發展出一個基於深度搜尋法 (depth-first search) 之演算流程，系統化求解各工作站中所有滿足需求的機器向量(machine vector)。利用此向量即可有效率求解零工式生產系統之網路可靠度。第二部分：為了考量管理者們對各目標具有不同的偏好，本研究以NSGA-II與TOPSIS 為基礎發展出一套方法， 以找出最佳之機器配置 (machine configuration) 來同時滿足網路可靠度最大化、成本最小化之目標。本研究採用男性襯衫之實際生產案例演示所提出之方法，不僅能在合理時間內計算出零工式生產系統之網路可靠度，且能依管理者對不同目標之偏好找出最佳的機器配置，提供管理者進行更進一步的決策與分析。

A job-shop production system (JPS) is a general manufacturing system. In a JPS,
each workstation configures multiple types of machines in order to increase flexibility of production. In a JPS, the number of normal machines in each workstation presents multiple levels due to partial failures, unexpected failures, and maintenance, etc. Therefore, it is suitable to state that the number of normal machines in each workstation is stochastic (i.e. multistate). To reflect the phenomenon of stochastic number of normal machines, network reliability can assess the performance of a JPS facing uncertain demand. The multi-objective optimization in this thesis is focusing on maximizing the
network reliability and minimizing the total cost of JPS, which most supervisors pursue. In order to solve the multi-objective optimization problem, we separate it into two parts. First, we transform JPS into a multistate job-shop production network (MJPN) by using network topology, proposing an algorithm to evaluate network reliability. The major difficulty in evaluating network reliability of the MJPN is that the state distribution is not determined. When the number of machine types is large, it is impossible to calculate the probability one by one. Therefore, a machine vector (MV), representing the current number of normal machines in a workstation, is introduced to overcome the difficulty. We propose an algorithm based on the depth-first search (DFS) with special expanding technique, to search all MVs, which satisfying demand. Second, to search the machine configuration (MF) with maximal network reliability and minimal total cost simultaneously, we propose a two-stage approach based on NSGA-II and TOPSIS. In addition, a real case of t-shirt production is utilized to illustrate the proposed method. Supervisors can apply it to find the proper MF based on their preference.

摘要................................................................................................................................ I
ABSTRACT .................................................................................................................. II
ACKNOWLEDGMENTS ........................................................................................... III
CONTENT ................................................................................................................... IV
LIST OF FIGURES ..................................................................................................... VI
LIST OF TABLES ..................................................................................................... VII
CHAPTER 1 INTRODUCTION ................................................................................... 1
1.1 Background and motivation ............................................................................. 1
1.2 Research objectives and purpose ..................................................................... 3
1.3 Organization of the thesis ................................................................................ 5
CHAPTER 2 LITERATURE REVIEW ........................................................................ 8
2.1 Job-shop production system ............................................................................. 8
2.2 Multistate network in manufacturing system ................................................... 9
2.3 Network reliability optimization .................................................................... 11
2.4 Multi-criteria decision analysis ...................................................................... 12
CHAPTER 3 EVALUATION OF MJPN RELIABILITY .......................................... 14
3.1. Multistate job-shop production network model ............................................ 15
3.2. Network reliability and capacity analysis ..................................................... 16
3.3. Generate all feasible MVs ............................................................................. 17
3.3.1 Depth-first search method .................................................................... 17
3.3.2 Expanding technique ............................................................................ 18
3.4. Algorithm for network reliability.................................................................. 21
3.5 A practical example ....................................................................................... 24
CHAPTER 4 MF PROBLEM DEFINITION AND A TWO-STAGE APPROACH
DEVELOPMENT ........................................................................................................ 30
4.1 MF problem formulation................................................................................ 32
4.2 Applying NSGA-II to find the Pareto solutions ............................................ 33
4.2.1 Non-dominated sorting approach and crowding distance assignment . 34
4.2.2 Evolution process and determining the new population ...................... 35
4.3 TOPSIS to determine the best compromise solution ..................................... 38
4.4 A comparison experiment of NSGA-II and SPEA2 ...................................... 40
CHAPTER 5 CASE STUDY ....................................................................................... 46
5.1 Garment manufacturing case ......................................................................... 46
CHAPTER 6 CONCLUSIONS AND FUTURE RESEARCH ................................... 53
6.1 Conclusions .................................................................................................... 53
6.2 Future research ............................................................................................... 54
REFERENCES ............................................................................................................ 56

Applegate, D. and W. Cook., “A computational study of the job-shop scheduling
problem”, ORSA Journal on Computing Vol. 3, no. 2, pp. 149-156 (1991).
Aven, T., “Reliability evaluation of multistate systems with multistate components”,
IEEE Transactions on Reliability, Vol. 34, no. 5, pp. 473-479 (1985).
Bai, G., Zuo, M. J., and Tian, Z. “Ordering heuristics for reliability evaluation of
multistate networks”, IEEE Transactions on Reliability, Vol. 64, no. 3, pp. 1015-
1023 (2015).
Becker, T., Meyer, M., and Windt, K., “A manufacturing systems network model for
the evaluation of complex manufacturing systems”, International Journal of
Productivity and Performance Management, Vol. 63, no. 3, pp. 324-340 (2014).
Brandimarte, P., “Routing and scheduling in a flexible job shop by tabu search”, Annals
of Operations Research, Vol. 41, no. 3, pp. 157-183 (1993).
Brucker, P. and Schlie, R., “Job-shop scheduling with multi-purpose machines”,
Computing, Vol. 45, no. 4, pp. 369-375 (1990).
Chang, P. C., “Reliability estimation for a stochastic production system with finite
buffer storage by a simulation approach”, Annals of Operations Research, pp. 1-15
(2017).
Chang, P. C. and Chen, S. H., “The development of a sub-population genetic algorithm
II (SPGA II) for multi-objective combinatorial problems”, Applied Soft Computing,
Vol. 9, no. 1, pp. 173-181 (2009).
Chang, P. C. and Lin, Y. K., “Fuzzy-based system reliability of a labour-intensive
manufacturing network with repair”, International Journal of Production Research,
Vol. 53, no. 7, pp. 1980-1995 (2015).
Chen, M. S. and Lan, C. H., “The maximal profit flow model in designing multipleproduction-
line system with obtainable resource capacity”, International journal
of production economics, Vol. 70, no. 2, pp. 175-184 (2001).
Cheong, C. Y., Tan, K. C., Liu, D., and Lin, C., “Multi-objective and prioritized berth
allocation in container ports”, Annals of Operations Research, Vol. 180, no. 1, pp.
63-103 (2010).
Chiang, T. C., Cheng, H. C., and Fu, L. C., “NNMA: An effective memetic algorithm
for solving multiobjective permutation flow shop scheduling problems”, Expert
systems with applications, Vol. 38, no. 5, pp. 5986-5999 (2011).
57
Czyzżak, P. and Jaszkiewicz, A., “Pareto simulated annealing—a metaheuristic
technique for multiple‐objective combinatorial optimization” Journal of Multi‐
Criteria Decision Analysis, Vol. 7, no. 1, pp. 34-47 (1998).
Dai, Y. S., Xie, M., and Wang, X., “A heuristic algorithm for reliability modeling and
analysis of grid systems”, IEEE Transactions on Systems, Man, and Cybernetics-
Part A: Systems and Humans, Vol. 37, no. 2, pp. 189-200 (2007).
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T.,. “A fast and elitist multiobjective
genetic algorithm: NSGA-II”, IEEE transactions on evolutionary computation, Vol.
6, no. 2, pp. 182-197 (2002).
Forghani-elahabad, M. and Mahdavi-Amiri, N., “A new efficient approach to search for
all multi-state minimal cuts”, IEEE Transactions on Reliability, Vol. 63, no. 1, pp.
154-166 (2014).
Garey, M. R., Johnson, D. S., and Sethi, R., “The complexity of flowshop and jobshop
scheduling”, Mathematics of operations research, Vol. 1, no. 2, pp. 117-129 (1976).
Gen, M., Cheng, R., and Lin, L., Network models and optimization: Multiobjective
genetic algorithm approach, Springer Science & Business Media (2008).
Hendry, L. C. and Kingsman, B., “Production planning systems and their applicability
to make-to-order companies”, European journal of operational research, Vol. 40,
no. 1, pp. 1-15 (1989).
Hudson, J. C. and Kapur, K. C., “Reliability bounds for multistate systems with
multistate component”, Operations Research, Vol. 33, no. 1, pp. 153-160 (1985).
Hwang, C. L. and Yoon, K., “Methods for multiple attribute decision making”, Multiple
attribute decision making, pp. 58-191 (1981).
Jacobs, F. R., Chase, R. B., and Lummus, R. R., Operations and supply chain
management, McGraw-Hill/Irwin New York, NY (2014).
Janan, X., “On multistate system analysis”, IEEE Transactions on Reliability, Vol. 34,
no. 4, pp. 329-337 (1985).
Jeyadevi, S., Baskar, S., Babulal, C., and Iruthayarajan, M. W., “Solving multiobjective
optimal reactive power dispatch using modified NSGA-II”, International Journal
of Electrical Power & Energy Systems, Vol. 33, no. 2, pp. 219-228 (2011).
Khare, V., Yao, X., and Deb, K., “Performance scaling of multi-objective evolutionary
algorithms”, International Conference on Evolutionary Multi-Criterion
Optimization (2003).