یک مطالعه موردی در مورد استفاده از الگوریتم های تکاملی برای بهینه سازی برنامه ریزی تولید آرد و محصولات نانوایی
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|26870||2013||11 صفحه PDF||سفارش دهید||6850 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Expert Systems with Applications, Volume 40, Issue 17, 1 December 2013, Pages 6837–6847
The production of bakery goods is strictly time sensitive due to the complex biochemical processes during dough fermentation, which leads to special requirements for production planning and scheduling. Instead of mathematical methods scheduling is often completely based on the practical experience of the responsible employees in bakeries. This sometimes inconsiderate scheduling approach often leads to sub-optimal performance of companies. This paper presents the modeling of the production in bakeries as a kind of no-wait hybrid flow-shop following the definitions in Scheduling Theory, concerning the constraints and frame conditions given by the employed processes properties. Particle Swarm Optimization and Ant Colony Optimization, two widely used evolutionary algorithms for solving scheduling problems, were adapted and used to analyse and optimize the production planning of an example bakery. In combination with the created model both algorithms proved capable to provide optimized results for the scheduling operation within a predefined runtime of 15 min.
Many bakery goods contain yeast (Saccharomyces cerevisiae) as a proofing agent. This form of proofing is a fermentation performed by microorganisms in which sugars are metabolized to CO2 (among other components), as can be seen in Fig. 1. Due to this fermentation process the production of such goods is not highly but strictly time sensitive from the point on, where the microorganisms get in contact with water and substrates under preferable conditions of temperature and humidity, as happens in the dough production process. Full-size image (30 K) Fig. 1. Sugar metabolisms in dough. Modified after (Collado-Fernández, 2003). Figure options The upmost shown metabolism is the most influential and most common in yeast containing doughs. Due to the common existence of lactic-acid bacteria in dough the lactic fermentation also occurs but rather influences the aroma than the texture of dough. The retention of CO2 produced by yeast is given by the dough matrix surrounding the gas bubbles and leads to a desired volume increase. Over time the amount of CO2 increases due to yeast activity and thus the gas pressure in the gas bubbles increases likewise. Up to a certain degree the dough matrix can withstand the structural stress induced by the increasing gas pressure, but after exceeding the maximum gas retention ability the dough matrix and thus its structure collapses more or less complete with respect to the present gas pressure and thus as a function of fermentation or proofing time. Cooling can be used to regulate or slow down the fermentation speed of yeast but is costly and sometimes accompanied with negative influence on the product quality. Due to this and the decrease of product quality (up to the total loss of marketability) induced by a too long unregulated fermentation process, the time dependency of the processing of yeast containing doughs has always to be considered in the production scheduling. Focusing on the German baking industry, the production planning is almost completely based on the practical experience of the responsible employee(s) instead of the usage of mathematical methods like in Scheduling Theory. Combined with the high diversity of the product range that includes around 100 different products in a common German bakery and the high complexity of the scheduling task induced therein, the performance of bakeries is often sub-optimal. The baking industry in Germany consists of approximately 14,000 producing companies, reaching business volume of almost 13.4 billion Euros per year and employs over 290,000 employees (Zentralverband des Deutschen Bäckerhandwerks e. V., 2012). Based on this general framework the increase of companies’ efficiency in respect of energy consumption or staff allocation and man working hours comprises high potential to decrease production costs in this industry. The use of evolutionary optimization algorithms like Particle Swarm Optimization (PSO) or Ant Colony Optimization (ACO) to solve the scheduling task might increase the efficiency of baking companies by calculating an optimal production plan and therefore determine the exact time schedule and capacities of devices needed to reach the production goal. Thus idle times of machines can be reduced or completely erased which leads to a reduction of energy consumption or the decrease in the makespan which leads to a reduction of man working hours needed. Kennedy and Eberhart (1995) invented PSO as an adaption of the movement and behavior of bird flocks or fish schools. As a swarm intelligence algorithm it mimics the behavior of such swarming animals and iteratively searches the search space of a given optimization problem for the optimal solution. Since its invention PSO was widely used to tackle numerous scheduling or optimization problems in many different industry branches (Bank et al., 2012, Eberhart and Shi, 2001, Li and Deng, 2012, Lian et al., 2008, Liao et al., 2012, Liu et al., 2010, Pan et al., 2008, Tang and Tang, 2012, Tasgetiren et al., 2007 and Wang and Yang, 2010). Another animal behavior inspired and frequently used algorithm (Ahmadizar, 2012, Li et al., 2010, Tzeng and Chen, 2012 and Yagmahan and Yenisey, 2010) is the Ant Colony Optimization, initially proposed by Dorigo in his Ph.D. thesis (Dorigo, 1992). ACO follows the mechanisms that help ants to find the shortest and thus optimal way between a food source and their formicary. Since ACO and PSO both provide easy implementation, easy modification and the ability to solve complex scheduling optimization tasks in reasonable computational time, they are promising methods to solve bakery scheduling tasks. In the presented work both methodologies were adapted to investigate the scheduling of an example bakery.
نتیجه گیری انگلیسی
The objective of this paper has been to develop a production planning procedure for the baking industry based on numerical modeling and evolutionary optimization algorithms. Therefore a model of the production processes that schedules the workflow of a given product sequence according to defined decision parameters was built in MATLAB. ACO and PSO have been used separately to solve the optimization task in respect to two different cost functions of economical interest. Both algorithms proved capable of solving the given optimization problem in a predefined time span of less than 15 min, to provide a procedure that can be employed shortly before the production start. Although ACO and PSO only provide local optima of the optimization problem, due to the limited runtime, even the worst case results of both algorithms for both cost functions yielded significant benefits compared to the results given by the initial product sequence. It seems very promising that the quality of the obtained optimization results could be enhanced by applying speed-up procedures to the employed algorithms or run the developed procedure on a PC with higher performance, to calculate more iterations or bigger particle or ant swarm sizes in the same computational time. Since both algorithms used seem to have slight advantages over each other, in respect to different optimization tasks, it would be interesting to investigate the performance of a method combining ACO and PSO for the presented bakery optimization problem, for example using one of the algorithms to provide a promising initial population for the respective other algorithm to work with.