带有一个不可用区间的两台平行机可拒绝排序问题（英文）  

Order Acceptance and Two Parallel Machines Scheduling Problem with an Availability Constraint

作　　者：池晶晶[1] 孙燕 

机构地区：[1]曲阜师范大学管理学院,日照市276826 [2]高密市柴沟镇王柱中心学校,山东省高密市261519

出　　处：《曲阜师范大学学报（自然科学版）》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)

摘　　要：本文主要研究两台平行机排序问题,其中一台机器上有一个固定的不可用区间。此外,生产商可以通过支付惩罚费用来拒绝工件。目标是极小化最大时间表长与惩罚费用之和。本文针对工件可恢复和不可恢复两种情形,分别给出了时间复杂性为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.

关 键 词：排序 拒绝 一个不可用区间 动态规划 

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