外人文献原文.pdf

A Multi-Objective Approach for both Makespan- and Energy-Effi cient Scheduling in Injection Molding Klaas D ahlmann(B)and J urgen Sauer Department of Computing Science, University of Oldenburg, Uhlhornsweg 84, 26129 Oldenburg, Germany klaas.daehlmann,juergen.saueruni-oldenburg.de Abstract. Recent sustainability eff orts require machine scheduling approaches to consider energy effi ciency in the optimization of sched- ules. In this paper, an approach to reduce power peaks while maintain- ing the makespan is proposed and evaluated. The central concept of the approach is to slowly equalize highs and lows in the energy input of the schedule without aff ecting the makespan through an iterative opti- mization. The approach is based on the simulated annealing algorithm to optimize machine schedules regarding the makespan and the energy input, using the goal programming method as the objective function. Keywords: Energy effi ciencyGoal programmingMulti-objective optimizationSchedulingSimulated annealing 1Introduction Large-scale facilities and devices such as industrial machines, air-condition, as well as computer and server systems may unnecessarily load the power grid if they are operated in parallel and especially if they have unsteady power con- sumption. Temporarily switching off one or many appliances not essential to the business processes may be one option to solve this problem. But, if the power consumption of the individual is known or well documented, the appli- ances may instead be parallelized in such a way that unnecessary peak loads can be avoided altogether without severely aff ecting the business processes. Espe- cially with regard to the scheduling of industrial machines, this concept may already be utilized at a predictive planning level to generate energetically ideal schedules without sacrifi cing an already good makespan. This paper therefore presents an approach for the optimization of the total energy input while maintaining a near-optimal makespan using the example of discontinuous plastics processing via injection molding machines. The approach is then examined through a combinatorial evaluation, describing, testing, and assessing diff erent, plausible parameter settings. The challenge herein is that the injection molding cycles of diff erent products and machines do not have the same duration and power consumption throughout c? Springer International Publishing AG 2016 G. Friedrich et al. (Eds.): KI 2016, LNAI 9904, pp. 141147, 2016. DOI: 10.1007/978-3-319-46073-4 12 142K. D ahlmann and J. Sauer the cycle as well as the fact that the highs and lows of the energy input are not equally spaced and symmetrical. The diff erent injection molding machines considered for this paper are shown in Table1. The steps cooling and melting start at the same time and run in parallel. Table 1. Individual steps, durations and power consumption of the injection molding cycles of the machines considered. StepEngel victory 750/140 techEngel ES 2550/400 HL KraussMaff ei KM420-2700C1 DurationPowerDurationPowerDurationPower Clamping3s1.8kW7s14.08kW5s14.85kW Nozzle1s1.2kW1s9.39kW1s9.9kW Injecting3s7.2kW6s56.31kW6s59.4kW Dwelling3s1.2kW5s9.39kW5s9.9kW Cooling11s4.22kW29s32.98kW27s34.79kW Melting7s5.98kW20s46.8kW22s49.37kW Opening3s0.32kW6s2.48kW7s2.62kW Ejecting1s0.4kW3s3.13kW0s3.3kW Demolding2s0.17kW0s1.34kW0s1.41kW Set-up25min-60min-150min- These issues, both machine scheduling and energy-effi cient production, have had increased recent consideration: Multi-objective optimization approaches for job and fl ow shop problems have been sucessfully used to either create the pareto front of possible solutions for an a posteriori evaluation 3,5 or to compare the results of diff erent local search heuristics for the special case of no-wait scheduling 10. Holistic simulation and forecasting systems have been employed to examine mutual dependencies and reciprocal eff ects regarding the energy effi ciency of the appliances 4,6 while evolutionary/genetic algorithms have been successfully utilized for energy optimization within the context of parallel machines and cloud service scheduling 9,11, pp. 191224. 2Approach As the scheduling of injection molding machines and jobs is based on combi- natorial and NP-hard optimization problems 1, p. 51, the trajectory-based simulated annealing algorithm 2,7 instead of a mathematically exact method is chosen. The initial solution is constructed while attempting to balance pro- duction jobs on the available machines, thereby minimizing the total makespan. The main objective of the optimization is to reduce the power peaks within the initial solution without negatively aff ecting the makespan while doing so. Minimizing the makespan by parallelizing as many jobs as possible increases the total energy input and may cause unwanted power peaks. However, trying A Multi-Objective Approach for Scheduling in Injection Molding143 to minimize energy consumption means to run as few machines as possible in parallel. In this paper, this dilemma will be counteracted by using the goal pro- gramming objective function to defi ne aspiration levels or goals for each objective and subsequently attempting to fi nd solutions to the scheduling problems con- sidered that reach these goals with the least deviation. As simulated annealing only genereates a single solution, a posteriori objective functions are not suited for further consideration. Goal programming on the other hand is an a priori objective function that permits an equal examination of all objectives 8. The goal factors are relative to the initial solution, e.g. a goal factor of 1 describes a goal value that is identical to the initial solution while goal factor of 1.5 and 0.5 means a goal value that is 50% larger or smaller respectively and a goal factor of 0 describes a utopian zero value. Because the objectives considered in multi-objective decision making are often measured on diff erent scales (in this case time in seconds and energy input in watts), a subsequent standardization of the scales is necessary to make them comparable. The solution is then rated using a distance function to determine the deviation between the current and the goal values. The neighborhood function used for the simulated annealing algorithm selects a random, active machine at the instant of time of a random power peak to shift the current and all future jobs one time unit towards the end, slowly resolving power peaks originating from unfavorable parallelization in the process. 3Evaluation The aim of the evaluation is twofold: On the one hand, diff erent distance func- tions are evaluated in their applicability for bi-objective optimization regarding time-based and energy-based objectives. On the other hand, as energy-effi cient optimization is a rather recent consideration, utopian and realistic goals for the power peak are compared with regard to their feasibility. The underlying idea of the evaluation is to systematically observe the behavior of the power peaks of the resulting schedules and to describe their dependency on the makespan, the objective function as well as the structure of the initial solution. 3.1Method To mimic the layout of the local company the machine data of which was obtained from, two machines of each type shown in Table1 will be assumed for the following evaluation, making a total of six machines. The simulated anneal- ing parameters remain unchanged for the entire evaluation. The algorithm starts at an initial temperature of 1 and is iteratively cooled by 1% until it reaches or falls below the minimal temperature of 0.01. Two diff erent initial solutions are examined in the evaluation. The fi rst solution assumes constant production on all machines after an initial setup time while the second solution consists of two to four equidistant changeovers to alternative product variants on each machine 144K. D ahlmann and J. Sauer during the observation period, depending on the size of the machine. The obser- vation period itself is a single work shift of 8h for all experiments. Three common distance functions are individually examined as objective functions for the goal programming method: The euclidean distance, the manhattan/taxicab distance, or the maximum/Chebyshev/chessboard distance. Moreover, six diff erent goals regarding the makespan are set and analyzed. A utopian goal with a makespan of zero as well as fi ve further goals, starting at a goal identical to the initial solutions makespan and increasing in 5% steps up to 20% more makespan. The last parameter of the evaluation is the goal factor for the power peak, with two diff erent goals being compared. The fi rst goal is the utopian goal as well while the second, realistic goal is calculated based on the average power peaks of the fi rst set of evaluations using the utopian goal. These parameters and their assignments make a total of 72 diff erent combinations. Each combination is then independently run 20 times to avoid some statistical deviation due to the random simulated annealing and neighborhood function. 3.2Results The results of the evaluation are divided into four categories, one for each com- bination of changeovers in the initial solution (with or without) and power peak goal factor (utopian or realistic). For reference, both initial solutions, with or without changeovers, have a duration of 8h and a power peak of 348.3kW. Without Changeover and Utopian Power Peak Goal Factor. A utopian goal for the makespan results in a plan that has only little improvement on the power peak but also does not increase the makespan at all. Results from makespan goal factor 1 depend on the chosen distance function: For the euclid- ean distance, the average power peak is identical to the solution using a utopian makespan goal while the makespan is slightly longer. For the manhattan dis- tance, the results are identical to the utopian makespan goal. For the maximum distance, the results are located in the same value range as those for makespan goal factor 1.1 to 1.2, as further described below. For the euclidean and the man- hatten distance, a makespan goal factor of 1.05 creates solutions that have their power peaks reduced by 20 to 15kW and are approximately 2min longer than the initial solution. For the maximum distance, the results are again in the same value range as those with from goal factor 1.1 to 1.2. Makespan goal factors 1.1, 1.15, and 1.2 generate results that decrease the power peak by roughly 30 to 40kW while increasing the makespan by about 3min. With Changeover and Utopian Power Peak Goal Factor. For the utopian makespan goal factor 0, the results for the euclidean and manhattan distance have their power peak reduced by about 30kW peak without aff ecting the makespan, while for the maximum distance, the power peak does not change much at all. Regarding the solutions for makespan goal factor 1, these are, in case of the manhattan distance, either identical to those obtained with a goal A Multi-Objective Approach for Scheduling in Injection Molding145 factor of 0, in case of the euclidean distance slightly longer but with identical power peak, or, in case of the maximum distance, located in the same value range as all further goal factors. The average results for makespan goal factors 1.05 to 1.2 have their power peaks reduced between 50 and 60kW while having their makespan increased by almost 2min. Without Changeover and Realistic Power Peak Goal Factor. When setting realistic goals for the power peak, the results of the euclidean distance are similar to those of the manhattan distance throughout all makespan goal factors. For goal factors 0 and 1, the results again show just little improvement of the power peak but do not increase the makespan. For the euclidean and manhattan distance, goal factor 1.05 results in solutions that have a roughly 10kW reduced power peak, just slightly better than those generated with goal factors 0 and 1, but have their makespan increased by about 2min. Results generated by makespan goal factors 1.1 to 1.2 have their power peaks reduced by 25 to 30kW while simultaneously having their makespan increased by about 3min. The results when using the maximum distance are signifi cantly diff erent from those described above. A utopian makespan goal creates almost no change at all for both the power peak and the makespan. Results from goal factors 1 to 1.2 have their power peaks reduced by roughly 20 to 30kW but at the same time have their makespan increased by up to 7min. With Changeover and Realistic Power Peak Goal Factor. The results for the euclidean and the manhattan distance are again comparable. Makespan goal factors 0 and 1 generate solutions with almost 30kW smaller power peaks while not increasing the makespan of the results. Goal factors 1.05 to 1.2 reduce the power peaks of the results even further by 55 to almost 60kW, but increase the makespan by 2min. The results generated using the maximum distance are again diff erent from those using the euclidean or manhattan distance. For a utopian makespan goal there is again no change for neither the power peak nor the makespan. For all other evaluated goal factors, the power peak is reduced by about 55 to 60kW, but the makespan progressively increases from 1min at goal factor 1 to 9min increase at goal factor 1.2. 3.3Discussion Several diff erent properties and behaviors can be derived from the evaluation: Regarding the behavior of the three distance functions examined, it is evident that there is no direct linear dependency between the makespan and the power peak. Allowing for an increase in makespan does not automatically imply a proportional reduction of the power peak. Instead, the power peaks of the solu- tion become more balanced and equalized with every iteration of the optimiza- tion, resulting in plans that cannot be further improved within the up to 20% makespan increase considered in the evaluation. This power peak limit is reached when using a makespan goal factor of 1.1 or higher, in some cases even earlier. 146K. D ahlmann and J. Sauer Continuing on to the individual analysis of the distance functions, the behav- ior of the euclidean and manhattan distance is comparable while the results generated using the maximum distance diff er signifi cantly. In general, when com- paring the results of the euclidean and manhattan distance, using a utopian power peak goal causes the individual solutions scatter more around the average solutions than they do when using a realistic power peak goal. When setting a utopian makespan goal, the euclidean and manhattan distance can create results that have a reduced power peak without aff ecting the makespan at all. The actual amount of improvement depends on the initial solution with just a slight improvement using a plan without changeovers to a more signifi cant improve- ment when starting from a solution with frequent changeovers. This is because it is more diffi cult to move power peaks to phases of low energy input when using a plan with constantly operating machines than it is when working with a plan that already has long phases of low energy input due to changeovers. In contrast, the results of the maximum distance diff er greatly from those described above. When setting a utopian makespan goal, only the makespan will be considered. But, as the initial solution is makespan-optimal already, the makespan cannot be further reduced, resulting in solutions that do not diff er much from the initial solution. When using a non-utopian goal for the makespan with a utopian goal for the power peak, it is the other way around. As a utopian power peak goal attempts to reduce the energy input by 100%, the mere 0 to 20% goals set by the makespan goal factors 1 to 1.2 are never taken into account, resulting in virtually identical average solutions for all makespan goal factors. The third and last case when using the maximum distance is the setting of realistic, attainable goals for both the makespan and the power peak. For these settings, the general characteristic of the maximum distance, as described above, becomes apparent. Contrary to the euclidean and manhattan distance, the max- imum distance attempts to reach all diff erent makespan goals, even if it does not provide any improvement for the power peak. 4Conclusion This paper presented and evaluated an approach and its parameters to retroac- tively optimize machine schedules, improving their energy effi ciency without signifi cantly worsening the already optimal makespan. As apparent from the results and the subsequent discussion, there is no consistently and uniformly best setting for all situations. Rather, the decision maker setting up the opti- mization and its goals needs to know the desired extent of the results. If small improvements of the power peak suffi ce, using the euclidean or manhattan dis- tance with utopian goals