Minimizing Makespan with Start Time-Dependent Jobs in a Two-Machine Flow Shop

The purpose of this paper is to consider the problem of scheduling a set of start time-dependent jobs ina two-machine flow shop, in which the actual processing times of jobs increase linearly according totheir starting time. The objective of this problem is to minimize the makespan. The problem is knownto be NP-hardness; therefore, there is no polynomial-time algorithm to solve it optimally in areasonable time. So, a branch-and-bound algorithm is proposed to find the optimal solution by meansof dominance rules, upper and lower bounds. Several easy heuristic procedures are also proposed toderive near-optimal solutions. To evaluate the performance of the proposed algorithms, thecomputational experiments are extracted based on the recent literature. Deteriorating jobs lead to anincrease in the makespan of the problems; therefore, it is important to obtain the optimal or near-optimalsolution. Considering the complexity of the problem, the branch-and-bound algorithm is capable of solvingproblems of up to 26 jobs. Additionally, the average error percentage of heuristic algorithms is less than1.37%; therefore, the best one is recommended to obtain a near-optimal solution for large-scale problems.