摘要
本文主要研究两台平行机排序问题,其中一台机器上有一个固定的不可用区间。此外,生产商可以通过支付惩罚费用来拒绝工件。目标是极小化最大时间表长与惩罚费用之和。本文针对工件可恢复和不可恢复两种情形,分别给出了时间复杂性为O(ns_1P^2)和O(np_(max)s_1P^2)的伪多项式时间动态规划算法.
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 dynamicprogramming is proposed for each to solve the problem optimally,which runs in time O(ns_1P^2)and O(np_(max)s_1P^2),respectively.
出处
《曲阜师范大学学报(自然科学版)》
CAS
2016年第1期36-41,共6页
Journal of Qufu Normal University(Natural Science)
基金
Special Funds of the National Natural Science Foundation(61340045)
Specialized Research Fund for the Doctoral Program of Higher Education(20123705110003)
Innovation Project of Shandong Graduate Education under Grant(SDYC13036)
关键词
排序
拒绝
一个不可用区间
动态规划
scheduling
rejection
an availability constraint
dynamic programming