HSZG Aktuell

23. April 2015


Thema: "Unrestricted Common Due Date Problem with Controllable Processing Times"


This months Informatik-Kolloquium on the 22nd April, witnessed the research work on the "Unrestricted Common Due Date Problem with Controllable Processing Times" by Abhishek Awasthi, a research associate at the Hochschule Zittau/Görlitz.


The unrestricted common due date problem with controllable processing times problem consists of scheduling jobs with controllable processing times on a single machine against a common due-date to minimize the overall earliness/tardiness and the compression penalties of the jobs. The objective of the problem is to find the processing sequence of jobs, the optimal reduction in the processing times of the jobs and their completion times. Important and novel properties were presented at this Kolloquium, along with an exact linear algorithm for optimizing a given job sequence for a single machine with a run-time complexity of O(n), where n is the number of jobs. The algorithm was explained with elaborate illustrations and explanations. Henceforth, the implementation of the polynomial algorithm in conjunction with a modified Simulated Annealing (SA) algorithm and Threshold Accepting (TA) was presented, to obtain the optimal/best processing sequence while comparing the two heuristic approaches


Abhishek Awasthi, M. Sc.

Enterprise Application Development Group (EAD)