混和流程排程(Hybrid Flow Shop Scheduling; HFS)的問題在許多真實製造產業中是非常常見的，例如：電腦組裝、TFT-LCD模板組裝，太陽能電池製造…等。過去大部分的研究皆在考慮時間需求底下的排程問題進而提高生產效率。然而，隨著全球碳排放量的增加導致加劇全球暖化問題，近年來大部分的國家或國際組織開始注重此議題並且制定相關機制來減少碳排放。現今，越來越多的製造業關注於節約能源的發展。
有鑑於此，本研究試圖從製造系統層面的觀點同時減少能源成本以及完工時間。本文首先針對考慮能源效率下之批量分割混和流程排程問題(Energy-Efficient Hybrid Flow Shop Scheduling with Lot Streaming; EEHFSLS)提出多目標混整數規劃法並同時最小化製造完工時間以及電力消耗，由於所提出的混整數規劃法之多目標存在權衡性質以及其計算的複雜性，本研究採用多目標基因演算法(Multi-Objectives Genetic Algorithm; MOGA)有效地求出近似的柏拉圖解。
此外，本研究所提出的多目標能源效率排程(Multi-Objectives Energy Efficiency Scheduling; MOEES) 演算法被使用來計算在多目標基因演算法中每條染色體的適應值。

he hybrid flow shop scheduling (HFS) problems are commonly encountered in many real-world manufacturing operations such as computer assembly, TFT-LCD module assembly, solar cell manufacturing etc. Most previous work considered the scheduling problem on time requirement to improving production efficiency. However, increasing amount of worldwide carbon emissions are intensifying to cause the global warming problem. Many countries or international organizations start to pay attention to this problem and formulate some mechanisms to reduce the carbon emission. Nowadays, manufacturing enterprises has also been growing interest in the development of energy savings. Thus, this research attempts to reduce energy cost and completion time from manufacturing system level perspectives.
The paper first proposed the multi-objective mixed integer programming to address the energy-efficient hybrid flow shop scheduling with lot streaming (EEHFSLS) to simultaneously minimize production makespan and electric power consumption. Due to the trade-off nature of both objectives and the computational complexity of proposed multi-objective mixed integer programming, this study adopts the Multi-Objectives Genetic Algorithm (MOGA) to obtain the approximate Pareto solutions, more efficiently. In addition, multi-objectives energy efficiency scheduling (MOEES) algorithm is also developed to calculate the fitness values of each chromosome within MOGA algorithm.

Table Lists v
Figures Lists vii
Chapter 1. Introduction 1
Chapter 2. Literature Review 5
2.1 Hybrid flow shop scheduling 5
2.2 Production scheduling in the sustainable manufacturing 8
Chapter 3. Energy-efficient hybrid flow shop scheduling with lot streaming (EEHFSLS) 11
3.1 Problem statement 11
3.2 A multi-objective mixed integer programming model for EEHFSLS 15
Chapter 4. Solution Algorithms 21
4.1 Non-Dominated Sorting Genetic Algorithm II (NSGA II) 21
4.1.1. Chromosome representation 23
4.1.2. Initialization population generation 25
4.1.3. Fitness evaluation 25
4.1.4. Non-Dominated Sorting 42
4.1.5. Selection operation 45
4.1.6. Crossover operation 45
4.1.7. Mutation operation 47
4.1.8. Replacement operation 48
4.1.9. Formation of elite population 48
4.1.10. Stopping criteria 48
Chapter 5. Experiment Studies 50
5.1 Performance evaluation of proposed NSGA II 50
5.1.1. Performance criteria 51
5.1.2. Description of test data 52
5.1.3. Parameter setting 53
5.1.4. Result and discussion 57
5.2 Parameter analysis 62
5.2.1. Preference vectors analysis 62
5.2.2. Analysis of unrelated parallel machines with different process power consumption 65
5.2.3. Analysis of each stage contains different machines 67
5.2.4. Analysis of the job containing sublots with different upper limit 70
Chapter 6. Conclusion and discussion 74
References 76

1.Adler, L., Fraiman, N., Kobacker, E., Pinedo, M., Plotnicoff, J.C. & Wu, T.P., BPSS: a scheduling support system for the packaging industry, Operations Research, 41(4), 1993, pp.641–648.
2.Allahverdi, A. & Mittenthal, J., Scheduling on M Parallel Machines Subject to Random Breakdowns to Minimize Expected Mean Flow Time, Naval Research Logistics, 41(5), 1994, pp.677–682.
3.Baker, K.R., Lot streaming in the two-machine flow shop with setup times, Annals of Operations Research, 57(1), 1995, pp.1–11.
4.Baker, K.R. & Jia, D., A comparative study of lot streaming procedures. OMEGA International Journal of Management Sciences, 21(5), 1993, pp.561–566.
5.Blackburn, J., Time-based competition, Encyclopedia of Business, 2nd ed, 1991. Retrieved January 25, 2014, from the World Wide Web:
http://www.referenceforbusiness.com/management/Str-Ti/Time-Based-Competition.html.
6.Bockerstette, J. & Shell, R., Time based manufacturing, McGraw-Hill, 1993.
7.Chang, J.H. & Chiu, H.N., A comprehensive review of lot streaming, International Journal of Production Research, 43(8), 2005, pp.1515–1536.
8.Chen, T.L. Chen, Y.Y. & Cheng C.Y., Variable lot-streaming scheduling in multi-stage hybrid flowshop problem – A case study for solar cell industry. International Journal of Production Research, 2013, Working paper.
9.Chiu, H.N., Chang, J.H. & Lee, C.H., Lot streaming models with a limited number of capacitated transporters in multistage batch production systems, Computers & Operations Research, 31(12), 2004, pp.2003–2020.
10.Czyzżak, P. & Jaszkiewicz, A., Pareto simulated annealing—a metaheuristic technique for multiple-objective combinatorial optimization, Journal of Multi-Criteria Decision Analysis, 7(1), 1998, pp.34–47.
11.Dai, M., Tanga, D., Giret, A., Salido, M. A. & Li, W.D., Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm, Robotics and Computer-Integrated Manufacturing, 29(5), 2013, pp.418–429.
12.Defersha, F.M. & Chen, M., A parallel genetic algorithm for dynamic cell formation in cellular manufacturing systems, International Journal of Production Research, 46(22), 2008, pp.6389–6413.
13.Defersha, F.M. & Chen, M., Mathematical model and parallel genetic algorithm for hybrid flexible flowshop lot streaming problem, The International Journal of Advanced Manufacturing Technology, 62(1-4), 2012, pp.249–265.
14.Fang, K., Uhan, N., Zhao, F. & Sutherland, J.W., A New Approach to Scheduling in Manufacturing for Power Consumption and Carbon Footprint Reduction, Journal of Manufacturing Systems, 30(4), 2011, pp.234–240.
15.Feldmann, M. & Biskup, D., Lot streaming in a multiple product permutation flow shop with intermingling, International Journal of Production Research, 46(1), 2008, pp.197–216
16.Gen, M., Lin, L. & Jo, J.B., Evolutionary Network Design by Multiobjective Hybrid Genetic Algorithm, Intelligent and Evolutionary Systems Studies in Computational Intelligence, 187, 2009, pp.105–121.
17.Gen, M. & Lin, L., Multiobjective evolutionary algorithm for manufacturing scheduling problems: state-of-the-art survey, Journal of Intelligent Manufacturing, 25(5), 2014, pp.849–866.
18.Glass, C.A., Gupta, J.N.D. & Potts, C.N., Lot streaming in three-stage process, European Journal of Operational Research, 75(2), 1994, pp.378–394.
19.Guinet, A.G.P. & Solomon, M.M., Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time, International Journal of Production Research, 34 (6), 1996, pp.1643–1654.
20.Gupta, J.N.D., Hariri, A.M.A. & Potts, C.N., Scheduling a two-stage hybrid flow shop with parallel machines at the first stage, Annals of Operations Research, 69(0), 1997, pp.171–191.
21.Gupta, J.N.D., Two-stage, hybrid flowshop scheduling problem, The Journal of the Operational Research Society, 39(4), 1988, pp.359–364.
22.Huang, W. & Li, S., A two-stage hybrid flowshop with uniform machines and setup times, Mathematical and Computer Modelling, 27(2), 1998, pp.27–45.
23.IEA, Tracking Industrial, Energy Efficiency and CO2 Emissions, 2007. Retrieved June , 2007, from the World Wide Web:
http://www.iea.org/publications/freepublications/publication/tracking_emissions.pdf
24.Jenabi, M., Fatemi Ghomi, S.M.T., Torabi, S.A. & Karimi, B., Two Hybrid Meta-heuristics for the Finite Horizon ELSP in Flexible Flow Lines with Unrelated Parallel Machines, Applied Mathematics and Computation, 186(1), 2007, pp.230–245.
25.Jin, Z. H., Ohno, K., Ito, T. & Elmaghraby, S. E., Scheduling Hybrid Flow Shops in Printed Circuit Board Assembly Lines, Production and Operations Management, 11(2), 2002, pp.216–230.
26.Kara, S., Manmek, S. & Herrmann, C., Global manufacturing and the embodied energy of products. CIRP Annals - Manufacturing Technology, 59(1), 2010, pp.29–32.
27.Lee, W.C. & Chung, Y.H., Permutation flowshop scheduling to minimize the total tardiness with learning effects, International Journal of Production Economics, 141(1), 2013, pp.327–334.
28.Lee, W.C., Wu, C.C., Chung, Y.H. & Liu, H.C., Minimizing the total completion time in permutation flow shop with machine-dependent job deterioration rates, Computers and Operations Research, 36(6), 2009, pp.2111–2121.
29.Liu, C.H. & Huang, D.H., Reduction of power consumption and carbon footprints by applying multi-objective optimisation via genetic algorithms, International Journal of Production Research, 52(2) , 2014, pp.337–352.
30.Liu, J., Single-job lot streaming in m − 1 two-stage hybrid flowshops, European Journal of Operational Research, 187(3), 2008, pp.1171–1183.
31.Li, W., Zein, A., Kara, S. & Herrmann, C., An Investigation into Fixed Energy Consumption of Machine Tools, Glocalized Solutions for Sustainability in Manufacturing, 2011, pp.268–273.
32.Low, C.Y., Hsu, C.J. & Su, C.T., A two-stage hybrid flowshop scheduling problem with a function constraint and unrelated alternative machines, Computers & Operations Research, 35(3),2008, pp.845–853.
33.Luo, H., Du, B., Huang, G.Q., Chen, H. & Li, X., Hybrid flow shop scheduling considering machine electricity consumption cost, International Journal of Production Economics, 146(2), 2013, pp.423–439.
34.Martin, C.H., A hybrid genetic algorithm/mathematical programming approach to themulti-family flowshop scheduling problem with lot streaming, OMEGA International Journal of Management Sciences, 37(1), 2009, pp.126–137.
35.Mori, M., Fujishima, M., Inamasu, Y. & Oda, Y., A study on energy efficiency improvement for machine tools. CIRP Annals - Manufacturing Technology, 60(1) , 2011, pp.145–148.
36.Mouzon, G. & Yildirim, M.B., A framework to minimize total energy consumption and total tardiness on a single machine, International Journal of Sustainable Engineering, 1(2), 2008, pp.105–116.
37.Mouzon, G., Yildirim, M.B. & Twomey J., Operational methods for minimization of energy consumption of manufacturing equipment. International Journal of Production Research, 45(18-19), 2007, pp.4247–4271.
38.Neugebauer, R., Wabner, M. & Rentzsch, H., Structure principles of energy efficient machine tools, CIRP Journal of Manufacturing Science and Technology, 4(2), 2011, pp.136–147.
39.Oĝuz, C. & Ercan, M.F., A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks. Journal of Scheduling, 8(4), 2005, pp.323–351.
40.Oğuz, C., Zinder, Y., Do, V.H., Janiak, A. & Lichtenstein, M., Hybrid flow-shop scheduling problems with multiprocessor task systems, European Journal of Operational Research, 152(1), 2004, pp.115–131.
41.Pinedo, M.L., Scheduling: Theory, Algorithms, and Systems, Prentice Hall, 2nd edition, 2000.
42.Potts, C.N. & Strusevich, V.A., Fifty years of scheduling: a survey of milestones, Journal of the Operational Research Society, 60, 2009, pp.S41–S68.
43.Rahimifard, S., Seow, Y. & Childs, T., Minimising Embodied Product Energy to support energy efficient manufacturing, CIRP Annals—Manufacturing Technology, 59(1), 2010, pp.25–28.
44.Reiter, S., A system for managing job shop production. Journal of Business, 39(3), 1966, pp.371–393.
45.Riane, F., Artiba, A. & Elmaghraby, S.E., Sequencing a Hybrid Two-stage Flowshop with Dedicated Machines, International Journal of Production Research, 40(17), 2002, pp.4353–4380.
46.Ribas, I., Leisten, R. & Framiñan, J.M., Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective, Computers & Operations Research, 37(8), 2010, pp.1439–1454.
47.Ruiz, R. & Maroto, C., A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility, European Journal of Operational Research, 169(3), 2006, pp.781–800.
48.Ruiz, R., Şerifoğlu, F.S. & Urlings, T., Modeling realistic hybrid flexible flowshop scheduling problems, Computers & Operations Research, 35(4), 2008, pp.1151–1175.
49.Ruiz, R. & Vázquez-Rodríguez, J.A., The Hybrid Flow Shop Scheduling Problem, European Journal of Operational Research, 205(1), 2010, pp.1–18.
50.Salvador, M.S, A solution to a special class of flow shop scheduling problems, Symposium on the Theory of Scheduling and Its Applications Lecture Notes in Economics and Mathematical Systems, 86, 1973, pp.83–91.
51.Şen, A., Topaloǧlu, E. & Benli, Ö.S., Optimal streaming of a single job in a two-stage flow shop, European Journal of Operational Research, 110(1), 1998, pp.42–62.
52.Seow, Y. & Rahimifard, S., A framework for modelling energy consumption within manufacturing systems. CIRP Journal of Manufacturing Science and Technology, 4(3), 2011, pp.258–264.
53.Solomon, S., Qin, D., Manning, M., Chen, Z., Marquis, M., Averyt K.B., Tignor, M. & Miller, H.L., Contribution of Working Group I to the Fourth Assessment Report of the Intergovernmental Panel on Climate Change, IPCC Fourth Assessment Report: Climate Change, 2007.
54.Tan, K.C., Goh, C.K., Yang, Y.J. & Lee, T.H., Evolving better population distribution and exploration in evolutionary multi-objective optimization, European Journal of Operational Research, 171(1), 2006, pp.463–495.
55.Ulungu, E.L., Teghem, J. & Ost, C., Efficiency of interactive multi-objective simulated annealing through a case study, Journal of the Operational Research Society, 49(10), 1998, pp.1044–1050.
56.Weinert, N., Chiotellis, S. & Seliger, G., Methodology for planning and operating energy-efficient production systems, CIRP Annals - Manufacturing Technology, 60(1), 2011, pp.41–44.
57.Wittrock, R.J., An adaptable scheduling algorithm for flexible flow lines, Operations Research, 36(3), 1988, pp.445–453.
58.Yang, J., A New Complexity Proof for the Two-stage Hybrid Flow Shop Scheduling Problem with Dedicated Machines, International Journal of Production Research, 48(5), 2010, pp.1531–1538.
59.Yao, F., Demers, A. & Shenker, S., A scheduling model for reduced CPU energy, Proceedings of the 36th annual symposium on foundations of computer science, 1995, pp.374–382.
60.Ying, K.C. & Lin, S.W., Multiprocessor task scheduling in multistage hybrid flow-shops: an ant colony system approach, International Journal of Production Research, 44(16), 2006, pp.3161–3177.
61.Zandieh, M. & Gholami, M., An Immune Algorithm for Scheduling a Hybrid Flow Shop with Sequence-Dependent Setup Times and Machines with Random Breakdowns, International Journal of Production Research, 47(24), 2009, pp.6999–7027.
62.Zitzler, E., Laumanns, M. & Thiele, L., SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization, Evolutionary Methods for Design, Optimisation, and Control, 2001, Barcelona, Spain: CIMNE, pp.95–100.
63.Zitzler, E. & Thiele, L., Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE Transactions on Evolutionary Computation, 3(4), 1999, pp.257–271.
64.Zhang, W., Yin, C., Liu, J. & Linn, R.J., Multi-job lot streaming to minimize the mean completion time in m-1 hybrid flowshops, International Journal of Production Economics, 96(2), 2005, pp.189–200.