A two-machine flow shop scheduling problem with controllable job processing times (Q1104846)

The two-machine flow-shop problem is considered in which processing times are decision variables. For each job, upper and lower limits on its processing time on the two machines are specified. The processing cost of each operation is a decreasing linear function of the selected processing time. The objective is to minimize the maximum completion time plus the total processing cost. The problem is shown to be NP-hard, thus justifying the use of two heuristics which are proposed. Both heuristics select a sequence of jobs and then use linear programming to find the processing times. The first heuristic uses an arbitrary sequence and is shown to have a worst-case performance ratio of 2. In the second heuristic, the sequence is obtained by solving a two-machine flow- shop problem with fixed processing times; this reduces the worst-case performance ratio to 3 / 2. Further analysis for this second heuristic provides some additional worst-case performance bounds which are dependent on the data.