We consider job scheduling on a flow-line production system, which covers a wide range of real-world manufacturing situations from plastic molding, steel milling to machine maintenance, and the service industry, where the duration of a task performed on a job is an arbitrary monotone non-decreasing function of the time the job has spent in the system. Our model is set in a deterministic environment with the initial conditions (i.e., job release timesrj) as decision variables (determined by the parametersγ1,γ2,...,γn, which control the time elapsed since the first machine becomes available). The main feature of the problem to minimize the sum of weighted completion timesas compared to, say, the problem to minimize the makespan considered earlier (Wagneur and Sriskandarajah (1993) )is that its solution depends on the rate of growth of the processing time functions. We confine our study to the two-machine case for the sake of simplicity. We derive a closed-form formula for the optimal job release times for a finite set of jobs. This result also applies to the problem to minimize the flow time as a special case.
- Deteriorating jobs
- Multiple-machine deterministic sequencing
- Optimal release times
- Weighted completion times
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics