Scheduling Problems with Linear Increasing Processing Times

We consider the scheduling problems with the time-dependent processing times. Each job i has a processing time y_i = p_i + v_it_i where p_i, v_i are positive constant and t_i is the starting time. All jobs become available for processing in time t = 1. We study the following problems. Problem 1.PN jobs have to be processed on a single machine. Each job i has a due date d_i. The problem is to find a schedule minimizing the maximum lateness i.e. max (C_i – d_i), where C_i denotes the completion time of job i.Problem 2.Problem 2. N jobs have to be processed on two parallel machines. The problem is to find a schedule minimizing the maximum completion time.Problem 3.Problem 3. N jobs have to be processed on two parallel machines. The problem is to find a schedule minimizing the sum completion time.We show NP-hardness problem 1 even though p_i = 0 for all jobs but one and we prove NP-hardness problem 2 and problem 3 even though p_i = 0 for all jobs.