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

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

Research time

2009 - 2013

Contact

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

Publications and talks (project related)

  • 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
  • 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
  • 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
  • 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
  • Talk with title: Job Shop Scheduling unter Berücksichtigung von   Fertigstellungsterminen. 12. Mitteldeutscher Doktorandenworkshop, Cottbus, 22.04.2010

Up