78. Total Earliness-Tardiness problems for Coupled of Tasks scheduling
Invited abstract in session TD-4: Application of integer programming, stream contributed papers.
Thursday, 14:45 - 16:15Room: C105
Authors (first author is the speaker)
| 1. | Gábor Galambos
|
| Applied Informatics, University of Szeged | |
| 2. | József Békési
|
| Department of Computer Algorithms and Artificial Intelligence, Faculty of Science and Informatics, University of Szeged | |
| 3. | Gyorgy Dosa
|
| Mathematical Department, University of Pannonia |
Abstract
We will consider the following problem. Given a Coupled Task Problem (CTP) with n jobs, and exact delay time between two tasks for each job. The objective function is to minimize the total earliness-tardiness (TET) of the schedule in one machine.
The practical applications of TET-problems are related to just-in-time production. Both, early and tardy production require special attention, because it is costly if the production performed earlier or later than the expected availability time. Therefore, ideally, optimal schedule occurs when the goods are ready for delivery when they should be available.
The structure of the due dates strongly affects both the value of the cost function and the complexity of the problem. We will present two results.
First, we consider the special problem, where distinct due dates are given for each job. We prove that this problem is NP-hard, and we present a complexity graph to show the open complexity cases related to the special cases of the problem.
In the second problem we will investigate a special case where the delay time and the processing time of the second tasks for each job is equal, and the processing time of the first job is not larger than the constant length of the second tasks. In the considered problem there is a common due date for each job and the due date is “large enough” related to the sum of the sizes of the jobs. For this problem we give a polynomial algorithm to get an optimal solution for the considered problem.
Keywords
- Complexity and efficiency of optimization algorithms
- Analysis and engineering of optimization algorithms
Status: accepted
Back to the list of papers