A closed-form solution for the optimal release times for the F2| deteriorating jobs |∑wjCjproblem

Research output: Journal article publicationJournal articleAcademic researchpeer-review


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) [23])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.
Original languageEnglish
Pages (from-to)1367-1376
Number of pages10
JournalDiscrete Applied Mathematics
Issue number13
Publication statusPublished - 6 Aug 2011


  • Deteriorating jobs
  • Multiple-machine deterministic sequencing
  • Optimal release times
  • Weighted completion times

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this