WS 21/22 (2 SWS + 1 SWS Präsentationskurs)

Veranstalterin: Christin Schumacher

Sprechstunde: nach Vereinbarung per Mail

Aktuelles

16.11.2021: Zeitplan aktualisiert

05.11.2021: Themenliste aktualisiert

29.10.2021: Zeitplan aktualisiert

16.09.2021: Zeitplan und Infos zu Ausarbeitung & Vortrag aktualisiert

02.09.2021: Vorläufige Themen und Infos zu Ausarbeitung & Vortrag aktualisiert

30.07.2021: Aktualisierung des Zeitplans mit Terminen zu Citavi, LaTex, Literaturrecherche sowie Teamkommunikation

27.07.2021: Zeitplan oben mit Terminen zu Citavi, LaTex, Literaturrecherche sowie Teamkommunikation aktualisiert

Inhalt

Optimierungsprobleme der Maschinenbelegungsplanung treten in der Wirtschaft in vielen Feldern auf. Der klassische Anwendungsfall von Maschinenbelegungsproblemen in der Produktion ist es zu entscheiden, in welcher Reihenfolge Produkte auf welchen Maschinen produziert werden sollen. Weitere Anwendungsfelder betreffen das Projektmanagement, die Reihenfolgeplanung im Krankenhaus, Flugpläne sowie Entladeprozesse im Logistikumfeld. Jedes Maschinenbelegungsproblem dieser Anwendungsfelder kann mit Hilfe der Graham Notation kategorisiert werden, sodass in der Forschung meist nur diese theoretische Einordnung des Problems betrachtet wird und Algorithmen oft anhand des theoretischen Problems designt werden können. So ist auch eine gute Übertragbarkeit auf weitere Probleme gewährleistet. Ziel des Seminars ist es, die Kategorisierung von Maschinenbelegungsproblemen zu beleuchten, Algorithmen für einige spezielle Maschinenbelegungsprobleme der Graham-Notation zu analysieren und ein Verständnis für den Aufbau von Heuristiken, Metaheuristiken sowie exakten Modellen für Optimierungsprobleme zu erlangen. Die Analyse der Probleme sowie die effiziente Lösung der Probleme mit Hilfe von Algorithmen steht im Vordergrund aller Seminarthemen.

Literatur

Zur Einführung in das Thema eignet sich folgende Literatur:

• Pinedo, Michael (2016): Scheduling. Theory, Algorithms, and Systems. 5. Aufl. Cham, Heidelberg, New York, Dordrecht, London: Springer.
• Ruiz, Rubén (2018): Scheduling Heuristics. In: Rafael Martí, Panos M. Pardalos und Mauricio G. C. Resende (Hg.): Handbook of Heuristics. Cham: Springer International Publishing, 1197-1229.
• Ruiz, Rubén; Vázquez-Rodríguez, José Antonio (2010): The hybrid flow shop scheduling problem. In: European Journal of Operational Research 205 (1), S. 1–18.
• Zhang, Jian; Ding, Guofu; Zou, Yisheng; Qin, Shengfeng; Fu, Jianlin (2019): Review of job shop scheduling research and its new perspectives under Industry 4.0. Journal of Intelligent Manufacturing, 30(4), 1809-1830. In: J Intell Manuf 30 (4), S. 1809–1830.

Themen

Die Themen orientieren sich an einzelnen wissenschaftlichen Artikeln aus der Forschung. Die jeweilige vorgegebene Literatur dient als Basislitertaur, die selbstständig durch die Studierenden durch weitere Literatur zum Thema ergänzt werden soll.

1. Konstruktive Algorithmen für hybride Flowshops am Beispiel von Low et al. (2008)
   
   Low, Chinyao; Hsu, Chou-Jung; Su, Chwen-Tzeng (2008): A two-stage hybrid flowshop scheduling problem with a function constraint and unrelated alternative machines. In: Computers & Operations Research 35 (3), S. 845–853. DOI: 10.1016/j.cor.2006.04.004.
   
   
2. Konstruktive Algorithmen für hybride Flowshops am Beispiel von Dios et al. (2018)
   
   Dios, Manuel; Fernandez-Viagas, Victor; Framinan, Jose M. (2018): Efficient heuristics for the hybrid flow shop scheduling problem with missing operations. In: Computers & Industrial Engineering 115, S. 88–99. DOI: 10.1016/j.cie.2017.10.034.
   
   
3. Konstruktive Algorithmen für hybride Flowshops am Beispiel von Jungwattanakit et al. (2009)
   
   Jungwattanakit, Jitti; Reodecha, Manop; Chaovalitwongse, Paveena; Werner, Frank (2009): A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. In: Computers & Operations Research 36 (2), S. 358–378. DOI: 10.1016/j.cor.2007.10.004.
4. NEH-Algorithmus am Beispiel von Allaoui/Artiba (2004)
   
   Allaoui, H.; Artiba, A. (2004): Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints. In: Computers & Industrial Engineering 47 (4), S. 431–450. DOI: 10.1016/j.cie.2004.09.002.
   
   
5. NEH-Algorithmus am Beispiel von Zandieh et al. (2010)
   
   Zandieh, M.; Mozaffari, E.; Gholami, M. (2010): A robust genetic algorithm for scheduling realistic hybrid flexible flow line problems. In: Journal of Intelligent Manufacturing 21 (6), S. 731–743. DOI: 10.1007/s10845-009-0250-5.
   
   
6. Tabu Suche am Beispiel von Kaczmarczyk et al. (2004)
   
   Kaczmarczyk, Waldemar; Sawik, Tadeusz; Schaller, Andreas; Tirpack, Thomas M. (2004): Optimal versus heuristic scheduling of surface mount technology lines. In: International Journal of Production Research 42 (10), S. 2083–2110. DOI: 10.1080/002075403010001647604.
   
   
7. Tabu Suche am Beispiel von Logendran et al. (2006)
   
   Logendran, Rasaratnam; deSzoeke, Paula; Barnard, Faith (2006): Sequence-dependent group scheduling problems in flexible flow shops. In: International Journal of Production Economics 102 (1), S. 66–86. DOI: 10.1016/j.ijpe.2005.02.006.
   
   
8. Variable Nachbarschaftssuche am Beispiel von Siqueira et al. (2018)
   
   Siqueira, E. C. de; Souza, M.J.F.; Souza, S. R. de (2018): A multi-objective variable neighborhood search algorithm for solving the hybrid flow shop problem. In: Electronic Notes in Discrete Mathematics 66, S. 87–94. DOI: 10.1016/j.endm.2018.03.012.
9. Iterated local search am Beispiel von Naderi et al. (2010)
   
   Naderi, B.; Ruiz, Rubén; Zandieh, M. (2010): Algorithms for a realistic variant of flowshop scheduling. In: Computers & Operations Research 37 (2), S. 236–246. DOI: 10.1016/j.cor.2009.04.017.
   
   
10. Simulated annealing am Beispiel von Elmi et al. (2013)
    
    Elmi, Atabak; Topaloglu, Seyda (2013): A scheduling problem in blocking hybrid flow shop robotic cells with multiple robots. In: Computers & Operations Research 40 (10), S. 2543–2555. DOI: 10.1016/j.cor.2013.01.024.
    
    
11. Simulated annealing am Beispiel von Jabbarizadeh et al. (2009)
    
    Jabbarizadeh, F.; Zandieh, M.; Talebi, D. (2009): Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints. In: Computers & Industrial Engineering 57 (3), S. 949–957. DOI: 10.1016/j.cie.2009.03.012.
    
    
12. Genetischer Algorithmus von Wu et al. (2003)
    
    Wu, Yi; Liu, Min; Wu, Cheng (2003): A genetic algorithm for solving flow shop scheduling problems with parallel machine and special procedure constraints. In: Stephen E. Chick (Hg.): Proceedings of the 2003 Proceedings of the Second International Conference on Machine Learning and Cybernetics. New York, N.Y, Piscataway, N.J: IEEE, S. 1774–1779.
    
    
13. Genetischer Algorithmus von Zabihzadeh et al. (2016)
    
    Zabihzadeh, Seyedeh Sarah; Rezaeian, Javad (2016): Two meta-heuristic algorithms for flexible flow shop scheduling problem with robotic transportation and release time. In: Applied Soft Computing 40, S. 319–330. DOI: 10.1016/j.asoc.2015.11.008.
    
    
14. Genetischer Algorithmus von Yaurima et al. (2009)
    
    Yaurima, Victor; Burtseva, Larisa; Tchernykh, Andrei (2009): Hybrid flowshop with unrelated machines, sequence-dependent setup time, availability constraints and limited buffers. In: Computers & Industrial Engineering 56 (4), S. 1452–1463. DOI: 10.1016/j.cie.2008.09.004.
    
    
15. Genetischer Algorithmus von Zandieh et al. (2010)  
    
    Zandieh, M.; Mozaffari, E.; Gholami, M. (2010): A robust genetic algorithm for scheduling realistic hybrid flexible flow line problems. In: Journal of Intelligent Manufacturing 21 (6), S. 731–743. DOI: 10.1007/s10845-009-0250-5.
    
    
16. Genetische Algorithmen BGA und SGAR von Urlings et al. (2010)
    
    Urlings, Thijs; Ruiz, Ruben; Serifoglu, Funda Sivrikaya (2010): Genetic algorithms with different representation schemes for complex hybrid flexible flow line problems. In: International Journal of Metaheuristics 1 (1), S. 30. DOI: 10.1504/IJMHEUR.2010.033122.
    
    
17. Genetische Algorithmen SGA von Urlings et al. (2010) und von Ruiz/Maroto (2006)
    
    Ruiz, Rubén; Maroto, Concepción (2006): A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. In: European Journal of Operational Research 169 (3), S. 781–800. DOI: 10.1016/j.ejor.2004.06.038.
    
    
18. Maschinenbelegungsplanung und Simulation mit genetischem Algorithmus anhand von Gholami et al. (2009)
    
    Gholami, M.; Zandieh, M.; Alem-Tabriz, A. (2009): Scheduling hybrid flow shop with sequence-dependent setup times and machines with random breakdowns. In: The International Journal of Advanced Manufacturing Technology 42 (1-2), S. 189–201. DOI: 10.1007/s00170-008-1577-3.
    
    
19. Maschinenbelegungsplanung und Simulation mit Simulated Annealing anhand von Allaoui/Artiba (2004)
    
    Allaoui, H.; Artiba, A. (2004): Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints. In: Computers & Industrial Engineering 47 (4), S. 431–450. DOI: 10.1016/j.cie.2004.09.002.
    
    

Ausarbeitung & Vortrag

Voraussetzungen für eine erfolgreiche Teilnahme:

• Es ist ein 15-minütiger Vortrag zum bearbeiteten Thema zu halten. Im Anschluss an jeden Vortrag findet eine Diskussion von 10-15 Minuten statt.
• Die Teilnahme an allen Vorträgen sowie die aktive Teilnahme an den Vorträgen von anderen Teilnehmenden ist verpflichtend.
• Es gilt, eine Ausarbeitung von 8-10 Seiten anzufertigen. Für die Ausarbeitungen soll LaTeX und die Vorlage der Universität verwendet werden. 
• Den Teilnehmenden wird sowohl für die Folien als auch für die Ausarbeitung ein:e Tandempartner:in zugeordnet. Die Tandempartner:innen geben sich gegenseitig schriftliches Feedback zu Folien und Ausarbeitung jeweils im Umfang von 1-2 Seiten. Alle Teilnehmenden handen somit am Ende des Seminars 2-4 Seiten Feedback für Ihre:n Tandemparter:in geschrieben. Das Feedback fließt in die Bewertung ein.

Organisatorisches

In Abhängigkeit von der dann aktuellen Lage wird das Seminar entweder als Onlineseminar über ZOOM oder als Präsenzveranstaltung abgehalten.