The three-machine proportionate flow shop problem with unequal machine speeds

CASISD OpenIR > 中国科学院科技政策与管理科学研究所(1985年6月-2015年12月)

	The three-machine proportionate flow shop problem with unequal machine speeds
	Hou, SX; Hoogeveen, H
发表期刊	OPERATIONS RESEARCH LETTERS
关键词	Proportionate Flow Shop Ordered Processing Times Machine Speeds V-shaped Makespan Dynamic Programmmg Nu Rho-hardness
摘要	In flow shop scheduling it is usually assumed that the processing times of the operations belonging to the same job are unrelated. But when a job corresponds to producing a certain quantity of some good. then it is likely that the processing times are related to this quantity, and hence are constant except for some factor that depends on the speed of the machine. In this paper, we consider this special case of the flow shop problem. which we call the proportionate flow shop problem with unequal machine speeds. This is a special case of the flow shop problem with ordered processing times that has been studied by Smith, Panwalkar, and Dudek. Their results imply that makespan minimization is easy if the first or last machine is slowest; if the second machine is slowest, then there exists an optimum schedule that is V-shaped. We provide an algorithm that solves this problem (and the more general problem with ordered processing times) to optimality in pseudopolynomial time, and we show that this is best possible by establishing, NP-hardness in the ordinary sense. (C) 2003 Published by Elsevier Science B.V.
	2003
卷号	31 期号:3 页码:7,225-231
ISSN	0167-6377
学科领域	Operations Research & Management Science
收录类别	SCI
语种	英语
WOS记录号	WOS:000182093800009
引用统计	被引频次：21[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://ir.casisd.cn/handle/190111/5266
专题	中国科学院科技政策与管理科学研究所(1985年6月-2015年12月)
推荐引用方式 GB/T 7714	Hou, SX,Hoogeveen, H. The three-machine proportionate flow shop problem with unequal machine speeds[J]. OPERATIONS RESEARCH LETTERS,2003,31(3):7,225-231.
APA	Hou, SX,&Hoogeveen, H.(2003).The three-machine proportionate flow shop problem with unequal machine speeds.OPERATIONS RESEARCH LETTERS,31(3),7,225-231.
MLA	Hou, SX,et al."The three-machine proportionate flow shop problem with unequal machine speeds".OPERATIONS RESEARCH LETTERS 31.3(2003):7,225-231.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
The three-machine pr（129KB）			开放获取	--	浏览