View article

Consider a flow shop with m machines in series and n jobs. Let pij denote the processing time of job j on machine i. The objective is to find a sequence for the n jobs that minimizes the makespan, denoted by Cmax. In the flow shop scheduling literature, the processing time of job j on machine i, pij, may be arbitrary, or may be a specific function of characteristics of the job and/or the machine [2, 6, 16]. In this paper we assume that job j has a processing requirement p j that affects the time job j spends on each one of the m machines. Furthermore, we assume that machine i has a characteristic value qi that affects the time each job spends on machine i. In what follows we consider models in which the time job j spends on machine i, pij, is a given function of p j and qi. The models may be regarded as so-called proportionate flow shops with processing times that are machine dependent.