An Optimal Scheduling Algorithm on Single-Machine with Two-Agent and Deteriorating Jobs

doi:10.7652/xjtuxb201606002

您当前的位置：

首页 >

文章列表页 >

An Optimal Scheduling Algorithm on Single-Machine with Two-Agent and Deteriorating Jobs

更新时间：2025-07-09

- An Optimal Scheduling Algorithm on Single-Machine with Two-Agent and Deteriorating Jobs
- Vol. 50, Issue 6, Pages: 9-14+82(2016)
- 作者机构：
  
  西安交通大学机械制造系统工程国家重点实验室,西安,710049
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201606002
  CLC： TP29
- Online First：10 June 2016，
  
  Published：2016
- 稿件说明：
移动端阅览
An Optimal Scheduling Algorithm on Single-Machine with Two-Agent and Deteriorating Jobs[J]. 2016, 50(6): 9-14+82.
DOI：

An Optimal Scheduling Algorithm on Single-Machine with Two-Agent and Deteriorating Jobs[J]. 2016, 50(6): 9-14+82. DOI： 10.7652/xjtuxb201606002.

摘要

针对单机床加工环境中待加工任务具有恶化效应且来自2个具有不同需求的代理时

无法快速求解出满足要求且成本最低的最优加工序列的情况

提出了可在特定约束条件下的具有恶化效应的双代理单机最优调度算法。首先提出优化目标为:保证一个代理的任务均不延迟完工的前提下

使得另一个代理的总加权完成时间或总加权折扣完成时间最小; 其次指出该优化问题具有NP难度

并给出其在一般及特殊情况下最优解的结构性质; 此后对于特定约束条件下的情形

提出多项式时间优化算法。该算法中首先将2个代理的任务分别按照所证明的最优策略排序

然后再按照使得2个代理能得到最小总加权完成时间和给定约束关系的算法将2个序列合并在一起

并证明得出的序列即为所求调度问题的最优解。实验结果表明

该算法作为确定性算法

计算时间与最优解平均误差率大于0.3%的模拟退火算法相似

远远低于可求解出最优解的分支定界算法。

Abstract

Two-agent single-machine scheduling problems with a deterioration job of which the actual processing time is defined as a function of its starting time are investigated. Optimization algorithms of polynomial time under some certain constraints are proposed. The optimization target of the problem is formulated as to minimize the total weighted completion time or total weighted discounted completion time of one agent while ensuring that all the jobs on the other agents are not delayed. This optimization problem is proved NP-hard and the structural properties of its optimal solutions under general and special conditions are illustrated. Optimization algorithms of polynomial time for solving these scheduling problems are proposed under some constraints. First

the jobs from two agents are respectively sequenced according to their optimal structural properties. Then

they are combined following the strategies that ensure the optimization target of two agents. Simulation results and comparisons with scheduling results of the simulated annealing(SA)and the branch-and-bound algorithms show that the CPU-times of the proposed algorithms are similar with the SA's that has an error rate greater than 0.3% with the optimal solutions

and much smaller than that of the branch-and-bound algorithm.

关键词

Keywords

references

GUPTA J N D, GUPTA S K. Single facility scheduling with nonlinear processing times [J]. Computers & Industrial Engineering, 1988, 14(4): 387-393.

ALIDAEE B, WOMER N K. Scheduling with time dependent processing times: review and extensions [J]. Journal of the Operational Research Society, 1999, 50(7): 711-720.

CHENG T C E, DING Q, LIN B M T. A concise survey of scheduling with time-dependent processing times [J]. European Journal of Operational Research, 2004, 152(1): 1-13.

赵传立, 张庆灵, 唐恒永. 具有线性恶化加工时间的调度问题 [J]. 自动化学报, 2003, 29(4): 531-535.

ZHAO Chuanli,ZHANG Qingling,TANG Hengyong. Scheduling problems under linear deterioration [J]. Acta Automatica Sinica, 2003, 29(4): 531-535.

赵晓丽, 唐立新. 带有线性恶化工件和释放时间的2个代理单机调度问题 [J]. 自动化学报, 2015, 41(1): 104-112.

ZHAO Xiaoli, TANG Lixin. Two-agent scheduling with linear-deteriorating jobs and release dates on a single machine [J]. Acta Automatica Sinica, 2015, 41(1): 104-112.

CHENG T C E, NG C T, YUAN J J. Multi-agent scheduling on a single machine with max-form criteria [J]. European Journal of Operational Research, 2008, 188(2): 603-609.

MOR B, MOSHEIOV G. Scheduling problems with two competing agents to minimize minmax and minsum earliness measures [J]. European Journal of Operational Research, 2010, 206(3): 540-546.

NONG Q Q, CHENG T C E, NG C T. Two-agent scheduling to minimize the total cost [J]. European Journal of Operational Research, 2011, 215(1): 39-44.

WU Wen-Hsiang, XU Jianyou, WU Wen-Hung, et al. A tabu method for a two-agent single-machine scheduling with deterioration jobs [J]. Computers Operations Re-search, 2013, 40(8): 2116-2127.

刘鹏, 周晓晔, 荣楠. 带有学习效应和恶化工件的双代理调度问题 [J]. 系统工程学报, 2012, 27(6): 841-846.

LIU Peng, ZHOU Xiaoye, RONG Nan. Two-agent scheduling with a learning effect and deteriorating jobs [J]. Journal of System engineering, 2012, 27(6): 841-846.

LIU Peng, YI Na, ZHOU Xiaoye. Two-agent singlemachine scheduling problems under increasing linear deterioration [J]. Applied Mathematical Modelling, 2011, 35(5): 2290-2296.

YIN Yunqiang, WU Chin-Chia, CHENG Shuenn-Ren. Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties [J]. Information Sciences, 2012, 189(7): 282-292.

AGNETIS A, BILLAUT J, GAWIEJNOWICZ S, et al. Multiagent scheduling-models and algorithms [M]. Berlin, Germany: Springer, 2014: 6-16.

YIN Y, CHENG T C E, WAN L, et al. Two-agent sing-le-machine scheduling with deteriorating jobs [J]. Computers Industrial Engineering, 2015, 81: 177-185.

JIN Y C. Minimizing total weighted completion time under makespan constraint for two-agent scheduleing with job-dependent aging effects [J]. Computers Industrial Engineering, 2015, 83: 237-243.

董春云,蔡远利.高超声速再入飞行器轨迹优化算法评估策略.2016,50(4):28-34.[doi:10.7652/xjtuxb201604005]

李国梁,张合新,周鑫,等.状态反馈事件触发控制系统的分析与设计.2016,50(5):146-150.[doi:10.7652/xjtuxb201605 022]

李小虎,柳松玮,施虎,等.基于两自由度H∞控制策略的泵控液压系统研究.2016,50(4):7-13.[doi:10.7652/xjtuxb 201604002]

杨航,刘凌,阎治安,等.双闭环Buck变换器系统模糊PID控制.2016,50(4):35-40.[doi:10.7652/xjtuxb201604006]

宋汝君,单小彪,李晋哲,等.压电俘能器涡激振动俘能的建模与实验研究.2016,50(2):55-60.[doi:10.7652/xjtuxb 201602010]

严惠云,张浩磊,刘小民.一种仿生鱼体自主游动的水动力学特性分析.2016,50(2):138-144.[doi:10.7652/xjtuxb2016 02023]

黄博,苑寿同,薛嘉伦.碳纤维气流扰动展纤器展纤过程仿真与实验.2015,49(12):19-25.[doi:10.7652/xjtuxb201512 004]

陈江城,张小栋,李睿,等.利用表面肌电信号的下肢动态关节力矩预测模型.2015,49(12):26-33.[doi:10.7652/xjtuxb201512005]

连峰,王婷婷,韩崇昭.多个不可分辨目标群的联合检测与估计误差界.2015,49(11):89-95.[doi:10.7652/xjtuxb2015 11015]

张蕾,张爱民,景军锋,等.静止无功补偿器与发电机励磁系统的自适应鲁棒协调控制策略2015,49(11):96-101.[doi:10.7652/xjtuxb201511016]

王海龙,王刚,陈曦,等.仿海蟹机器人游泳足水动力学分析与实验研究.2015,49(8):75-83.[doi:10.7652/xjtuxb 201508013]

刘冠初,熊静琪,乔林,等.四足机器人自由步态规划建模与算法实现.2015,49(6):84-89.[doi:10.7652/xjtuxb201506 014]

董恩清,刘伟,宋洋.采用三角形节点块处理无线传感器网络节点定位中节点翻转歧义的迭代方法.2015,49(4):84-90.[doi:10.7652/xjtuxb201504014]

卜祥伟,吴晓燕,张蕊,等.双曲正弦非线性跟踪微分器设计.2015,49(1):107-111.[doi:10.7652/xjtuxb201501018]

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Integrated and Joint Design Optimization of Centrifugal Compressor Impeller and Casing Treatment at Multiple Working Points

A Fast Calculation Method for Thermal Flow Fields in Transformer Windings Based on PI-DeepONet

Windage Loss and Flow Characteristics in Impeller Back Gaps of sCO2 Radial Inflow Turbines

Knowledge Graph Representation Learning Driven by Semantic Discrimination and Subgraph Integration

Effects of Steam Addition on the Swirl Combustion and Emission Characteristics of Cracked Ammonia

Related Author

No data

Related Institution

No data

⁰