## Abstract

This paper aims to illustrate a flow shop scheduling problem in which the processing time of each operation of job j is equal to p_{j}. This class of the flow shop problem is known as the proportionate flow shop problem. A proportionate flexible flow shop problem is generalization of the proportionate flow shop problem with multiple identical machines at any stage. The general WSPT rule minimizes the total weighted completion time in the case of a single machine. Unfortunately, this result cannot be generalized to parallel machines. We propose a decomposition approach applied to a Restricted Master Problem (RMP) with a set covering formulation in which the linear programming relaxation is solved efficiently by column generation. If the linear programming relaxation forms to be integral, an optimal solution for the problem is obtained. Otherwise, we apply a branch and bound algorithm which is based on the completion time of jobs appearing in a fraction solution, through some computational results, the effectiveness and the capability of solving large scale problems. Finally, the proposed approach is proven to be able to effectively minimize the total weighted completion time for the proportionate flexible flow shop problem by some analyses.

Original language | English |
---|---|

Pages (from-to) | 417-422 |

Number of pages | 6 |

Journal | Proceedings of the IASTED International Conference on Modelling, Simulation, and Optimization |

Publication status | Published - 2004 Dec 27 |

Event | Proceedings of the Fourth IASTED International Conference on Modelling, Simulation, and Optimization - Kauai, HI, United States Duration: 2004 Aug 17 → 2004 Aug 19 |

## All Science Journal Classification (ASJC) codes

- Software
- Modelling and Simulation
- Computer Science Applications