Lower and Upper Bounds for flow shop scheduling problems withdue date constraints

摘要

The problem of scheduling n jobs on m machines is one of the classical problems known as thernflow shop scheduling problem that has interested researchers for many years. The nature of thernflow shop scheduling problem varies as the assumptions change. The underlying assumptions inrnthe problem we study are as follows:rn· all jobs follow the same sequence of machines,rn· a machine can only process one job at a time and once a job starts on a machine, it must bernprocessed to completion,rn· the setup times of the operations are included in the processing times and do not depend onrnthe sequence,rn· each job has a due date associated with it,rn· a job is ready for processing at or after its release time and must be completed by its due date,rn· the objective is to minimize the makespan.