Scheduling with generalized batch delivery dates and earliness penalties

CSpace

	Scheduling with generalized batch delivery dates and earliness penalties
	Yang, XG
	2000-08-01
发表期刊	IIE TRANSACTIONS
ISSN	0740-817X
卷号	32 期号:8 页码:735-741
摘要	In this paper, we study some single machine scheduling problems with generalized batch delivery dates and earliness penalties. The generalized delivery dates are given a-priori before any jobs are processed. They are unrelated to the jobs and the processing order. Each specific delivery batch contains jobs completed but undelivered until the specific delivery date. We consider scheduling problems to minimize two types of earliness penalties: one is the total earliness; the other is the maximum earliness. For these two problems, first we show that they are NP-hard in the strong sense for general cases; then we prove that they are still NP-hard even if there are only two generalized batch dates. We also prove that they are solved in polynomial time for general earliness penalty function if all processing times are equal, acid give an O(n log(n)) algorithm to solve the weighted earliness cases.
语种	英语
WOS研究方向	Engineering ; Operations Research & Management Science
WOS类目	Engineering, Industrial ; Operations Research & Management Science
WOS记录号	WOS:000087725500006
出版者	KLUWER ACADEMIC PUBL
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/15695
专题	中国科学院数学与系统科学研究院
通讯作者	Yang, XG
作者单位	Chinese Acad Sci, Inst Syst Sci, Lab Management Decis Informat Syst, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Yang, XG. Scheduling with generalized batch delivery dates and earliness penalties[J]. IIE TRANSACTIONS,2000,32(8):735-741.
APA	Yang, XG.(2000).Scheduling with generalized batch delivery dates and earliness penalties.IIE TRANSACTIONS,32(8),735-741.
MLA	Yang, XG."Scheduling with generalized batch delivery dates and earliness penalties".IIE TRANSACTIONS 32.8(2000):735-741.