Scheduling of a Two-machine Flowshop with Processing Time Linearly Dependent on Job Waiting-time

Abstract

This paper deals with the problem of finding the minimum finish-time schedule in a two-machine flowshop, where the processing times of jobs are linearly dependent on the job waiting-times. The problem is shown to be NP-hard. A heuristic algorithm is presented, and the worst-case bounds are derived for the different variations of the algorithm.

Keywords:

• analysis
• computers
• heuristics
• optimization
• scheduling