TY - CHAP A1 - Herrmann, Frank T1 - Scheduling a flow-shop with simultaneously loaded stations T2 - Proceedings of the International Annual Conference of the German Operations Research Society 2012,(OR 2012), September 4 - 7, Hannover KW - Fließfertigung KW - Flow-shop-Problem KW - Reihenfolgeproblem Y1 - 2012 ER - TY - CHAP A1 - Herrmann, Frank T1 - Genetic algorithm with simulation for scheduling of a flow shop with simultaneously loaded stations T2 - Proceedings of the 28th EUROPEAN Conference on Modeling and Simulation, May 27th - 30th, 2014, Brescia, Italy N2 - In this study, a real world flow shop with a transportation restriction is regarded. This restriction reduces the set of feasible schedules even more than the no-buffer restrictions discussed in the literature in the case of limited storage. Still this problem is NP-hard. Since this scheduling problem is integrated in the usual hierarchical planning, the tardiness is minimised. Compared to even specific priority rule for this class of problems the suggested genetic algorithm delivers significant better results. The specific structure of this class of problems complicates the calculation of the performance criteria. This is solved by a simulation algorithm. Proceedings 28th European Conference on Modelling and Simulation. KW - Ablaufplanung KW - Hierarchische Produktionsplanung KW - Flow-shop-Problem KW - Reihenfolgeproblem KW - Genetischer Algorithmus KW - simulation of restrictions KW - scheduling KW - flow-shop KW - no-buffer (blocking) KW - no-wait KW - genetic algorithm KW - real world application Y1 - 2014 UR - http://www.scs-europe.net/dlib/2014/ecms14papers/simo_ECMS2014_0076.pdf ER - TY - JOUR A1 - Herrmann, Frank T1 - Scheduling a flow shop with simultaneously loaded stations: A real world application JF - Journal of Control Science and Engineering N2 - Companies use special designed flow shops, in order to satisfy specific demands. Products need to be transported (from one station to the next station) by a crane and the way of working of this crane excludes the intermediate storage (of a work piece). In addition, the way of working restricts the set of feasible schedules even more than the no-buffer restriction discussed in the literature in the case of limited storage. Since this scheduling problem is integrated in the usual hierarchical planning, the tardiness is minimised. A linear optimisation model is presented to provide a formal description of this NP-hard problem. It is also used to explain the performance of priority rule based heuristic solutions on small test problems. In detail, priority rules as well as a priority rule based branch and bound procedure are analysed; priority rules are regarded, because a priority rule is still the standard procedure for on-line scheduling in industrial practise. Out of successful priority rules in the literature the best one is identified by an extensive simulative investigation. An improved look-ahead is realised by a restricted search over all possible schedules. KW - Fließfertigung KW - Flow-shop-Problem KW - Scheduling KW - Real world flow shop with restrictions KW - No buffer and no wait KW - Minimising tardiness KW - Optimisation model KW - Priority rules KW - Priority rule based branch and bound procedure Y1 - 2015 U6 - https://doi.org/10.17265/2328-2231/2015.03.004 VL - 3 SP - 147 EP - 163 ER - TY - CHAP A1 - Herrmann, Frank T1 - Simulation based priority rules for scheduling of a flow shop with simultaneously loaded stations T2 - Proceedings of the 27th EUROPEAN Conference on Modeling and Simulation, May 27th - 30th, 2013, Ålesund, Norway N2 - In this study, a real world flow shop with a transportation restriction is regarded. This restriction reduces the set of feasible schedules even more than the no-buffer restrictions discussed in the literature in the case of limited storage. Since this scheduling problem is integrated in the usual hierarchical planning, the tardiness is minimised. This NP-hard problem is solved by priority rules, because of the addressed dynamic environment (and a high number of jobs) at the company site. Due to the technological restrictions the real duration of a job is significantly larger than its net processing time. By a simulation of the processing time many priority rules are improved and some even significantly. With extensive simulations successful priority rules in the literature are analysed. KW - simulation of processing time KW - scheduling KW - flow-shop KW - no-buffer (blocking) KW - no-wait KW - priority rules KW - real world application KW - Hierarchische Produktionsplanung KW - Flow-shop-Problem KW - Reihenfolgeproblem Y1 - 2013 U6 - https://doi.org/10.7148/2013-0775 SP - 775 EP - 781 ER - TY - CHAP A1 - Metlicka, Magdalena A1 - Davendra, Donald A1 - Herrmann, Frank A1 - Meier, Markus A1 - Amann, Matthias T1 - GPU accelerated NEH algorithm T2 - Proceedings of the 2014 IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS), Orlando, FL, 09.-12. Dec. 2014 N2 - This research aims to develop a CUDA accelerated NEH algorithm for the permutative flowshop scheduling problem with makespan criterion. NEH has been shown in the literature as the best constructive heuristic for this particular problem. The CUDA based NEH aims to speed up the processing time by utilising the GPU cores for parallel evaluation. In order to show the versatility and scalability of the CUDA based NEH, four new higher dimensional Taillard sets are generated. The experiments are conducted on the CPU and GPU and pairwise compared. Percentage relative difference and paired t-test both confirm that the GPU based NEH significantly improves on the execution time compared to the sequential CPU version for all the high dimensional problem instances. KW - Flow-shop-Problem KW - CUDA KW - Graphics processing units KW - Instruction sets KW - Kernel KW - Parallel processing KW - Synchronization KW - Algorithm design and analysis KW - Arrays KW - Parallelverarbeitung Y1 - 2014 U6 - https://doi.org/10.1109/CIPLS.2014.7007169 SP - 114 EP - 119 ER - TY - CHAP A1 - Herrmann, Frank T1 - Perturbation in Local Search for Scheduling T2 - Proceedings of the 29th EUROPEAN Conference on Modeling and Simulation, May 26th - 29th, 2015, Albena, Bulgaria N2 - Local search is an established meta heuristic for scheduling problems. To avoid of getting stucked in a local optimum, the achieved solution is destroyed. Usually, this is done randomly. Here, two problem specific procedures are suggested. One focuses on jobs with the highest difference between the actual processing time and the net processing time of the job and the other one tries to remove jobs which causes the highest idle time for themselves or other jobs. Comprehensive simulations of test scheduling problems as well as a real world application show that both problem specific procedures outperform a random procedure. KW - Ablaufplanung KW - Lokales Suchverfahren KW - Local search KW - Perturbation KW - Scheduling KW - Flow shop KW - Flow-shop-Problem Y1 - 2015 U6 - https://doi.org/10.7148/2015-0446 ER - TY - CHAP A1 - Davendra, Donald A1 - Herrmann, Frank A1 - Bialic-Davendra, Magdalena T1 - Scheduling tardiness constrained flow shop with simultaneously loaded stations using Genetic Algorithm T2 - Proceedings of the 4th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence (ISMSI 2020): Thimphu, Kingdom of Bhutan during March 21-22, 2020 N2 - In this study, a real world flow shop with a transportation restriction is regarded. This restriction reduces the set of feasible schedules even more than the no-buffer restrictions discussed in the literature in the case of limited storage. Still this problem is NP-hard. Since this scheduling problem is integrated in the usual hierarchical planning, the tardiness is minimised. Compared to even specific priority rule for this class of problems the suggested genetic algorithm delivers significant better results. The specific structure of this class of problems complicates the calculation of the performance criteria. This is solved by a simulation algorithm. KW - simulation of restrictions KW - scheduling, KW - flow-shop KW - no-buffer (blocking) KW - no-wait KW - genetic algorithm KW - real world application KW - Ablaufplanung KW - Hierarchische Produktionsplanung KW - Flow-shop-Problem KW - Reihenfolgeproblem KW - Genetischer Algorithmus Y1 - 2020 U6 - https://doi.org/10.1145/3396474.3396475 PB - ACM ER -