Job Sequencing with Exponential Functions of Processing Times

Article type: Research Article

Authors: Janiak, Adam | Kovalyov, Mikhail Y.

Affiliations: Institute of Computer Engineering, Control and Robotics, Wroclaw University of Technology, Janiszewskiego 11/17, 50-372 Wroclaw, Poland, e-mail: [email protected] | Faculty of Economics, Belarus State University, and United Institute of Informatics Problems, National Academy of Sciences of Belarus, Skorini 4, 220050 Minsk, Belarus, e-mail: [email protected]

Abstract: We study single machine scheduling problems, where processing times of the jobs are exponential functions of their start times. For increasing functions, we prove strong NP-hardness of the makespan minimization problem with arbitrary job release times. For decreasing functions, maximum lateness minimization problem is proved to be strongly NP-hard and total weighted completion time minimization problem is proved to be ordinary NP-hard. Heuristic algorithms are presented and computationally tested for these problems.

Keywords: scheduling, single machine, start time dependent processing times, computational complexity, heuristics

Journal: Informatica, vol. 17, no. 1, pp. 13-24, 2006