曲阜师范大学学报（自然科学版）Issue(1)：36-41,6.DOI:10.3969/j.issn.1001-5337.2016.1.036
带有一个不可用区间的两台平行机可拒绝排序问题
Order Acceptance and Two Parallel Machines Scheduling Problem with an Availability Constraint
摘要
Abstract
This paper considers a two parallel machines scheduling problem,which one machine has a fixed availability constraint and the manufacturer can reject orders by paying penalties.The objective is to mini-mize the makespan of the accepted orders plus the total penalties of the rejected orders.Two cases,resumable and nonresumable are discussed in this paper.Moreover,a pseudo-polynomial time algorithm based on dynamic programming is proposed for each to solve the problem optimally,which runs in time O (ns 1 P 2 )and O (np max s 1 P 2 ),respectively.关键词
排序/拒绝/一个不可用区间/动态规划Key words
scheduling/rejection/an availability constraint/dynamic programming分类
数理科学引用本文复制引用
池晶晶,孙燕..带有一个不可用区间的两台平行机可拒绝排序问题[J].曲阜师范大学学报（自然科学版）,2016,(1):36-41,6.基金项目
Special Funds of the National Natural Science Foundation （61340045）；Specialized Research Fund for the Doctoral Pro-gram of Higher Education （20123705110003）；Innovation Project of Shandong Graduate Education under Grant （SDYC13036）． （）
