Combined column generation and constructive heuristic for a proportionate flexible flow shop scheduling

Yueh-Min Huang, Der Fang Shiau

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


In a proportionate flow shop problem, jobs have to be processed through a fixed sequence of machines, and processing time for each job is equal on all machines. Such a problem has seldom been tackled. Proportionate flexible flow shop (PFFS) scheduling problems combine the properties of proportionate flow shop scheduling problems and parallel machine scheduling problems. This study presents a combined approach based on column generation (CG) for a PFFS problem with the criterion to minimize the objective of the total weighted completion time (TWCT). Minimizing TWCT in a PFFS problem significantly differs from the parallel-identical-machine scheduling problem, an optimal schedule in which jobs on each machine are in the weighted shortest processing time (WSPT) order. This combined approach adopts a CG approach to effectively handle job assignments to machines, and a constructive heuristic to obtain an optimal sequence for a single machine. Experimental results show the effectiveness of the combined approach in obtaining excellent quality solutions in a reasonable time, especially for large-scale problems.

Original languageEnglish
Pages (from-to)691-704
Number of pages14
JournalInternational Journal of Advanced Manufacturing Technology
Issue number7-8
Publication statusPublished - 2008 Sept 1

All Science Journal Classification (ASJC) codes

  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Combined column generation and constructive heuristic for a proportionate flexible flow shop scheduling'. Together they form a unique fingerprint.

Cite this