Flexible Flow Shop with Storage: Complexity and Optimisation Methods
- Publication Type:
- Conference Proceeding
- IFAC-PapersOnLine, 2016, 49 (12), pp. 237 - 242
- Issue Date:
© 2016 The paper is concerned with a two-stage flexible flow shop with a buffer under the assumption that all operations have the same processing time and that each job can be processed on a machine only if a certain amount of buffer space is allocated to this job. The amount of buffer space to be allocated differs from job to job. The buffer is shared by all machines and has limited size. The objective function is the makespan. The application area includes supply chains which involve loading and unloading operations, and problems arising in computer systems with shared memory. It is proven that in general, the problem is NP-hard in the strong sense, but in the case of two-machines, it is solvable in polynomial-time. For the general case, several integer linear programming models are presented and compared by means of computational experiments. The presented integer linear programming models implement various ideas such as symmetry breaking constraints, knapsack type cutting planes and the results of the analysis of the structure of optimal schedules.
Please use this identifier to cite or link to this item: