A COMBINATORIAL PROPERTY OF PALLET-CONSTRAINED TWO MACHINE FLOW SHOP PROBLEM IN MINIMIZING MAKESPAN  

作　　者：HOU Sixiang Han Hoogenveen Petra Shuurman 

机构地区：[1]Institute [2]of [3]Systems [4]Engineering [5]China [6]National

出　　处：《Journal of Systems Science & Complexity》2002年第4期416-422,共7页系统科学与复杂性学报（英文版）

基　　金：This author is supported by Netherlands organization for international cooperation in high education.

摘　　要：We consider the problem of scheduling n jobs in a pallet-constrained flow shop so as to minimize the makespan.In such a flow shop environment,each job needs a pallet the entire time,from the start of its first operation until the completion of the last operation,and the number of pallets in the shop at any given time is limited by a positive integer,K≤n.Generally speaking,the optimal schedules may be passing schedules.In this paper,we present a combinatorial property which shows that for two machines,K(K≥3）pallets,there exists a no-passing schedule which is an optimal schedule for n≤2K-1 and 2K-1 is tight.

关 键 词：Scheduling flow shop PALLETS makespan. 

分 类 号：O226[理学—运筹学与控制论]