W pracy rozpatrywany jest jednomaszynowy problem szeregowania zadań z czasami wykonywania opisanymi liniową funkcją zależną od momentu rozpoczęcia ich wykonywania. Optymalizacji podlega suma opóźnień zadań. Badany problem jest NP-trudny nawet w przypadku stałych czasów wykonywania zadań, dlatego w celu jego rozwiązania skonstruowano szereg algorytmów przybliżonych, w których wykorzystano własności wykazane dla jego szczególnych przypadków. Jakość rozwiązań generowanych przez skonstruowane algorytmy została porównana eksperymentalnie.
The paper deals with a single machine scheduling problem for the total tardiness minimization. The job processing time is given as start time dependent linear function, which contains two parts. The first part denotes a fixed processing time and the second part (characterized by a growth rate) describes the job processing time deterioration. Since the classical version of the latter problem is NP-hard, we constructed three approximation algorithms to solve its special cases. The algorithms were developed based on the problem properties, which were proved in the paper. In order to compare the quality of proposed algorithms, we performed a numerical experiment.