摘要(英) |
Abstract
Scheduling is one of the most important problems in any manufacturing industry.
Therefore, the problem has been studied extendedly. Since, the scheduling problem is classified
as NP-hard problem, which means the time required for finding the optimal solution of the
problem is grown exponentially with the size of the problem. Therefore, it is unrealistic to find
optimal solution for the scheduling problem in the scene of the real world industrial case, even
with today advanced computer system.
There are many heuristic algorithms have been proposal to solve the scheduling problem.
They are beam search, local search technique, tabular search and Genetic Algorithm (GA), to
name a few. In recent years, GA has become a noticeable candidate for solving the scheduling
problem effectively. The idea of mimicking the evolutionary process is very interesting to
researchers. And the recent advanced in heuristic GA has sparked more attention toward new
research and application in the field of GA.
In Brewery industry, the fermentation process is the most crucial components of the whole
manufacturing process. It will decide the quality, taste of the products as well as the
productivity of the production line. Since, the fermentation time can take up to 41 days, and the
requirement time is varying a lot between different types of beers, therefore finding a good
scheduling solution to dealing with this complexity is crucial for beer manufacturers. This
research will propose a GA to solve the scheduling problem in beer production. The proposed
methodology will serve as a planning and analysis tool to utilize assets (tanks, filling lines)
effectively, reduce congestion and synchronize the production process between the two
production stages (liquid preparation and bottling).
Keywords: scheduling, lot sizing, brewery industry, two-stage production, GA. |
參考文獻 |
References
[1] Adams J, Balas E, Zawack D. (1988). The Shifting Bottleneck Procedure for Job Shop
Scheduling. Management Science. Vol 34(3), pp. 391-401.
[2] Amin-Naseri MR, Afshari AJ. (2012). A hybrid genetic algorithm for integrated process
planning and scheduling problem with precedence constraints. The International Journal
of Advanced Manufacturing Technology. Vol 59(1), pp. 273-287.
[3] Baldo TA, Santos MO, Almada-Lobo B, Morabito R. (2014). An optimization approach
for the lot sizing and scheduling problem in the brewery industry. Computers &
Industrial Engineering. Vol 72, pp. 58-71.
[4] Chang Wook A, Ramakrishna RS. (2002). A genetic algorithm for shortest path routing
problem and the sizing of populations. IEEE Transactions on Evolutionary Computation.
Vol 6(6), pp. 566-579.
[5] Cheng R, Gen M, Sasaki M. (1995). Film-copy deliverer problem using genetic
algorithms. Computers & Industrial Engineering. Vol 29(1), pp. 549-553.
[6] Cheng R, Gen M, Tsujimura Y. (1996). A tutorial survey of job-shop scheduling
problems using genetic algorithms—I. representation. Computers & Industrial
Engineering. Vol 30(4), pp. 983-997.
[7] Ferreira D, Clark AR, Almada-Lobo B, Morabito R. (2012). Single-stage formulations
for synchronised two-stage lot sizing and scheduling in soft drink production.
International Journal of Production Economics. Vol 136(2), pp. 255-265.
[8] Ferreira D, Morabito R, Rangel S. (2009). Solution approaches for the soft drink
integrated production lot sizing and scheduling problem. European Journal of
Operational Research. Vol 196(2), pp. 697-706.
[9] Fleischmann B, Meyr H. (1997). The general lotsizing and scheduling problem.
Operations-Research-Spektrum. Vol 19(1), pp. 11-21.
58
[10] Gao J, Gen M, Sun L, Zhao X. (2007). A hybrid of genetic algorithm and bottleneck
shifting for multiobjective flexible job shop scheduling problems. Computers &
Industrial Engineering. Vol 53(1), pp. 149-162.
[11] Gen M, Gao J, Lin L. Multistage-Based Genetic Algorithm for Flexible Job-Shop
Scheduling Problem. In: Gen M, Green D, Katai O, McKay B, Namatame A, Sarker RA,
et al., (Eds.) Intelligent and Evolutionary Systems. Berlin, Heidelberg: Springer Berlin
Heidelberg; (2009), pp. 183-196.
[12] Haupt R. (1989). A survey of priority rule-based scheduling.
Operations-Research-Spektrum. Vol 11(1), pp. 3-16.
[13] Inagaki J, Haseyama M, Kitajima H. (1999). A genetic algorithm for determining
multiple routes and its applications. Circuits and Systems, 1999 ISCAS ′99 Proceedings
of the 1999 IEEE International Symposium on. Vol 6, pp. 137-140.
[14] Kacem I, Hammadi S, Borne P. (2002). Approach by localization and multiobjective
evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions
on Systems, Man, and Cybernetics, Part C (Applications and Reviews). Vol 32(1), pp.
1-13.
[15] Kundakci N, Kulak O. (2016). Hybrid genetic algorithms for minimizing makespan in
dynamic job shop scheduling problem. Computers & Industrial Engineering. Vol 96, pp.
31-51.
[16] Leu G, Namatame A. Evolving Failure Resilience in Scale-free Networks. Intelligent
and Evolutionary Systems (2008), pp. 49-59.
[17] Lin L, Gen M. (2009). Auto-tuning strategy for evolutionary algorithms: balancing
between exploration and exploitation. Soft Computing. Vol 13(2), pp. 157-168.
[18] Mitsuo G, Runwei C, Lin L. Network Models and Optimization: Multiobjective Genetic
Algorithm Approach. 1st ed. London: Springer-Verlag London; (2008).
[19] Orito Y, Jun T, Takeda M, Yamamoto H. Index Fund Optimization Using Genetic
59
Algorithm and Scatter Diagram Based on Coefficients of Determination. Intelligent
and Evolutionary Systems (2009), pp. 1-11.
[20] Pezzella F, Morganti G, Ciaschetti G. (2008). A genetic algorithm for the Flexible
Job-shop Scheduling Problem. Computers & Operations Research. Vol 35(10), pp.
3202-3212.
[21] Toledo CFM, de Oliveira L, Pereira RD, Franca PM, Morabito R. (2014). A genetic
algorithm/mathematical programming approach to solve a two-level soft drink
production problem. Computers & Operations Research. Vol 48, pp. 40-52.
[22] Xia H, Li X, Gao L. (2016). A hybrid genetic algorithm with variable neighborhood
search for dynamic integrated process planning and scheduling. Computers & Industrial
Engineering. Vol 102, pp. 99-112.
[23] Xia W, Wu Z. (2005). An effective hybrid optimization approach for multi-objective
flexible job-shop scheduling problems. Computers & Industrial Engineering. Vol 48(2),
pp. 409-425.
[24] Zhang H, Gen M, Seo Y. (2006). An effective coding approach for multiobjective
integrated resource selection and operation sequences problem. Journal of Intelligent
Manufacturing. Vol 17(4), pp. 385-397. |