Two-Machine Open Shop Scheduling with Proportionally Deteriorating Jobs and Makespan Objective

This manuscript examines the two-machine open shop scheduling problem where the latter a job is scheduled the longer it takes to process this job. The performance is measured by minimizing the makespan. By modifying existing algorithms for the corresponding problem with fixed processing times, two new algorithms are developed for the problem under consideration. The proofs of optimality of both algorithms are presented. The execution of these algorithms is illustrated by two numerical examples. Finally, both algorithms are further modified to solve a more generalized problem where the time demanded to process a job is a general linear function of its beginning time.