摘要
讨论两台机器上工件具有嵌套关系处理集限制并且可拒绝的排序问题。每个工件具有各自的加工时长和拒绝费用,且可在符合其特性的机器上进行加工,或者被拒绝并支付相应的拒绝费用。可加工某工件的机器的集合,称为此工件的处理集。任意两工件的处理集具有嵌套关系,即相互包含或不相交。本文所讨论目标函数是最小化机器的时间表长与总拒绝费用的和,将给出最坏情形比为2的近似算法。
This paper is about the problem of scheduling jobs on two machines with nested processing set restrictions and rejection.Each job has its processing time and rejection penalty,which can be processed on a machine that matches its characteristics,or can be rejected and paid the corresponding rejection penalty.The collection of machines that can process a job is called the processing set of this job.The processing set of any two jobs has a nested relationship,that is,it contains or does not intersect with each other.The objective on this problem is to minimize the machines'makespan with the sum of total rejection penalty.We will give approximate algorithms with a worst-case ratio of 2.
作者
丁甜甜
慕运动
柴幸
DING Tiantian;MU Yundong;CHAI Xing(College of Science,Henan University of Technology,Zhengzhou 450001,China)
出处
《周口师范学院学报》
CAS
2022年第5期8-12,共5页
Journal of Zhoukou Normal University
基金
国家自然科学青年基金“工件流程时间的若干排序问题”(12001169)。
关键词
嵌套关系处理集
拒绝费用
时间表长
近似算法
排序
Nested processing sets
rejection penalty
makespan
approximate algorithm
scheduling
