2003 | OriginalPaper | Chapter
Single Machine Scheduling Problems with Exponentially Start Time Dependent Job Processing Times
Authors : Aleksander Bachman, Adam Janiak, Mikhail Y. Kovalyov
Published in: Operations Research Proceedings 2002
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The paper deals with single machine scheduling problems, where job processing times are given by exponentially start time dependent functions. We consider decreasing and increasing functions of job processing times. For the increasing functions, we proved ordinary and strong NP-hardness of the makespan minimization problem under ready times restrictions. We obtained the same results, i.e., ordinary and strong NP-hardness, for the maximum lateness minimization problem, but for the decreasing functions of job processing times. We proved also ordinary NP-hardness for the total weighted completion time minimization, under the assumption that job processing times are characterized by decreasing functions.