W zależności od ilości danych do przetworzenia generowanie pliku może się wydłużyć.

Jeśli generowanie trwa zbyt długo można ograniczyć dane np. zmniejszając zakres lat.

Artykuł

Pobierz BibTeX

Tytuł

Single Machine Scheduling with Due Date Assignment to Minimize the Total Weighted Lead Time Penalty and Late Work

Autorzy

[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] pracownik

Dyscyplina naukowa (Ustawa 2.0)

[2.3] Informatyka techniczna i telekomunikacja

Rok publikacji

2023

Opublikowano w

Omega

Rocznik: 2023 | Tom: vol. 121

Typ artykułu

artykuł naukowy

Język publikacji

angielski

Słowa kluczowe
EN
  • Scheduling
  • Due Date Assignment
  • Lead Time Penalty
  • Late Work
  • NP-hard
Streszczenie

EN We study a single machine scheduling problem with due date assignment for minimizing the total weighted lead time penalty and late work, where the lead time penalty is the excess of an assigned due date over a given lead time, and the late work is the part of a job executed after the assigned due date. For the problem with common due date assignment, we show that it is solvable in O(n log n) time. For the problem with unrestricted due date assignment, we determine an optimal due date assignment for a given schedule, and transform the problem to an equivalent problem for minimizing the total [Image 1]-shape function, where [Image 1] depicts the shape of the penalty function for a job in relation to its completion time. Furthermore, we show that the problem with unrestricted due date assignment is unary NP-hard by proving the unary NP-hardness of the equivalent problem, and study two special cases. For the case with identical lead times, we show that it is binary NP-hard by providing a dynamic programming algorithm. While for the case with identical processing times, we prove that it is solvable in O(n3) time. Finally, we study the problem of minimizing the total [Image 1]-shape function, and show that its two special cases are binary NP-hard by proving that they are pseudo-polynomially solvable.

Data udostępnienia online

28.06.2023

DOI

10.1016/j.omega.2023.102923

URL

https://www.sciencedirect.com/science/article/abs/pii/S0305048323000877?via%3Dihub

Uwagi

Article Number: 102923

Punktacja Ministerstwa / czasopismo

140

Impact Factor

6,7

Ta strona używa plików Cookies, w celu zapamiętania uwierzytelnionej sesji użytkownika. Aby dowiedzieć się więcej przeczytaj o plikach Cookies i Polityce Prywatności.