Martin Luther University Halle-Wittenberg

Further settings

Login for editors

Job Shop Scheduling in consideration of Due Dates

Overview

Scope and Objectives

The topic of this research project is the well-known Job Shop Scheduling Problem in consideration of given due dates. Time goals, as the minimization of the number of late jobs or the minimization of the average tardiness, become economic important because the breach of due dates can cause a contract penalty. The aim of this project is the development and the comparison of problem specific heuristics and on neighborhood based localsearch methods that are managed by metaheuristics.

Short Description

In multitude of industries there are several service providers that take production orders from other companies. Thereby every order  (= job) has to be executed on a given set and special sequence of different machines. Due to the different sequences according to the working machines, we want to answer the question which machine schedule has to be chosen.

Previous research results mostly consider the situation with the objective of minimizing the makespan (= the entire completion time). In consideration of due dates there are differentiated objective functions, e.g. the minimization of the number of late jobs. The exploration and answer of such Job Shop Scheduling Problems is the topic of this research project.

Basic literature:

  • Michael L. Pinedo: Scheduling - Theory, Algorithms and Systems, 3. Auflage, Springer-Verlag, New York, 2008
  • Simon French: Sequencing and Scheduling - an Introduction to the Mathematics of the Job Shop, Ellis Horwood Ltd., 1981
  • Günther Zäpfel, Roland Braune: Moderne Heuristiken der Produktionsplanung, Verlag Franz Vahlen, München, 2005

Specific literature:

  • Stephan Kreipl: A large step random walk for minimizing total weighted tardiness in a job shop, Journal of Scheduling 2000, Issue 3, p. 125-138
  • Svetlana Kravchenko: Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem, Discrete Applied Mathematics 98 (2000), p. 209-217
  • Yazid Mati, Stéphane Dauzère-Pérès, Chams Lahlou: A general  approach for optimizing regular criteria in the job-shop scheduling  problem. European Journal of Operational Research 212 (1), p. 33-42

Research time

2009 - 2014

Contact

The research project is conducted by Dipl.-Wirt.-Math. Jens Kuhpfahl ()

Publications (project related)

  • Kuhpfahl, J.; Bierwirth, C.: A Study on Local Search  Neighborhoods for the Job Shop Scheduling Problem with Total Weighted  Tardiness Objective, submitted for publication
  • Kuhpfahl, J., Bierwirth, C.: A GRASP approach for the Job  Shop Scheduling Problem with minimizing the Total Weighted Tardiness,  In: Proceedings of 6th  Multidisciplinary International Scheduling  Conference: Theory and  Applications (MISTA 2013), 613-616
  • Zhang, R., Kuhpfahl, J.: Corrigendum to "A simulated annealing algorithm  based on block properties for the job shop scheduling problem with  total weighted objective" [Computers and Operations Research 38(2011)  854-867], Computers & Operations Research40 (2013), 2816,Link   
  • Kuhpfahl, J., Bierwirth, C.: A New Neighbourhood Operator for the  Job Shop Scheduling Problem with Total Weighted  Tardiness Objective,  In: Applied Mathematical  Optimization and Modelling - APMOD  2012 Extended Abstracts, 204-209
  • Kuhpfahl, J., Bierwirth, C.: Computational Comparison of  Neighbourhoods for the Job Shop Scheduling Problem with Total Weighted  Tardiness Objective, In: Proceedings of 5th Multidisciplinary  International Scheduling Conference: Theory and Applications (MISTA  2011), 536-538, Link    

Talk overview

  • Talk with title: A GRASP approach for the job shop scheduling problem with the  objective of minimizing the total weighted tardiness, OR 2013 - The  International Conference on Operations Research, Rotterdam (Netherlands), 05.09.2013
  • Talk with title: A GRASP approach for the Job Shop Scheduling Problem with minimizing the Total Weighted Tardiness, 6th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2013), Ghent (Belgium), 29.08.2013
  • Talk with title: A new Method for the Evaluation of a Neighbor Solution in  Local Search Procedures for Solving the JSPTWT, EURO XXVI - European  Conference on Operational Research 2013, Rom, 01.07.2013
  • Talk with Title: Job Shop Scheduling with Consideration of Due Dates, Talk in Research Colloquium, Halle, 17.05.2013
  • Talk with title: A GRASP Approach for the Job Shop Scheduling Problem with Total Weighted Tardiness Objective, EURO XXV 2012, European Conference  on Operational Research, Vilnius (Litauen), 09.07.2012
  • Talk with title: Job Shop Scheduling with consideration of due dates, 14th PhD Workshop Nordost, Wittenberg, 11.05.2012
  • Talk with title: A New Neighbourhood Operator for the Job Shop Scheduling  Problem with Total Weighted Tardiness Objective. International Conference of Applied Mathematical Optimization and Modelling (APMOD 2012), Paderborn, 28.03.2012
  • Talk with title: A Computational Study of Local Search Neighbourhoods for  the Job Shop Scheduling Problem with a Tardiness Objective. International Conference on Operations Research (OR 2011), Zurich (CH),   31.08.2011
  • Talk with title: Computational Comparison of Neighbourhoods for the Job Shop Scheduling Problem with Total Weighted Tardiness Objective. 5th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2011), Phoenix (USA), 10.08.2011
  • Talk with title: Job Shop Scheduling unter Berücksichtigung von Fertigstellungsterminen. 12th PhD Workshop Nordost, Cottbus, 22.04.2010

Algorithms and Data

Up