工件带简单线性恶化函数和共同交货期单机排序问题

doi:10.12005/orms.2016.0020

运筹与管理 ›› 2016, Vol. 25 ›› Issue (1): 154-157.DOI: 10.12005/orms.2016.0020

工件带简单线性恶化函数和共同交货期单机排序问题

余英¹, 舒彤², 曾春花¹

1.凯里学院数学科学学院,贵州凯里 556011;
2.湖南大学工商管理学院,湖南长沙 410000

收稿日期:2014-05-13 出版日期:2016-02-25
作者简介:余英(1981-),女,浙江桐庐人,副教授,研究方向为排序理论和组合最优化。
基金资助:
国家自然科学基金项目(71172194);贵州省科技厅与凯里学院2014年度省校合作协议项目:(黔科合LH字[2014]7232);贵州凯里学院院级课题自科类重点课题(Z1402);贵州省科技厅、黔东南州科技局、凯里学院科技联合基金(黔科合字LKK[2013]30号)

Scheduling Simple Linear Deteriorating Jobs On a Single Machine with Common Due Date

YU Ying¹, SHU Tong², ZENG Chun-hua¹

1.School of Mathematical Science KaiLi University, Kaili 556011, China;
2.School of Business HuNan University, ChangSha 410000, China

Received:2014-05-13 Online:2016-02-25

摘要/Abstract

摘要： 本文研究单机排序问题,其中工件加工时间具有简单线性恶化函数.同时,所有工件均具有一个给定共同交货期.目标函数为最小化提前有奖延误受罚之和.在逆一致性条件下,给出了求解该排序问题的一个伪多项式时间动态规划算法.同时借助于几何舍入技巧,对求解这类排序问题给出了一个充分多项式时间的近似算法(FPTAS)。

关键词: 单机排序, 动态规划算法, 近似算法(FPTAS), 几何舍入技巧

Abstract: A single machine scheduling problem with simple linear deterioration processing time is studied.The due date times of all jobs are assumed to be common simultaneously. Our aim is to find an optimal sequence so as to minimize the total of the earliness award and tardiness penalty. A pseudo-polynomial time solvable dynamic algorithm is addressed to it under inverse agreeable ratio condition. We also propose a fully polynomial time solvable approximation scheme(FPTAS) to that problem by geometric rounding technique.

Key words: single machine scheduling, dynamic algorithm, approximation scheme, geometric rounding technique

中图分类号:

O223

余英, 舒彤, 曾春花. 工件带简单线性恶化函数和共同交货期单机排序问题[J]. 运筹与管理, 2016, 25(1): 154-157.

YU Ying, SHU Tong, ZENG Chun-hua. Scheduling Simple Linear Deteriorating Jobs On a Single Machine with Common Due Date[J]. Operations Research and Management Science, 2016, 25(1): 154-157.

参考文献

[1] Alidaee B, Womer N K. Scheduling with time dependent processing time:review and extensions[J]. Journal of Operational Research Society, 1999, 50(5): 711-720.
[2] 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-13.
[3] Mosheiov G. Scheduling jobs under simple linear deterioration[J]. Computer and Operations Research, 1994, 21: 653- 659.
[4] Mosheiov G. Complexity analysis of job-shop scheduling with deteriorating jobs[J]. Discrete Applied Mathematics, 2002, 117: 195-209.
[5] Wang J B, Xia Z Q. Scheduling jobs under decreasing linear deterioration[J]. Information Processing Letters, 2005, 94(2): 63- 69.
[6] Wang J B, Xia Z Q. Flow shop scheduling problems with deteriorating jobs under dominating machines[J]. Journal Operation Research Society, 2006, (57): 220-226.
[7] Wang J B, Lin L, Shan F. Single machine group scheduling problems with deteriorating jobs[J]. Int J Adv Manuf Technol, 2008, (39): 808- 812.
[8] Oran D. Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times[J]. Computer Operational Research, 2008, (35): 2071-2078.
[9] Wang Dan, Wang J B. Single-machine scheduling with simple linear deterioration to minimize earliness penalty[J]. Int J Adv Manuf Technol, 2010, (46): 285-290.
[10] Yang S H, Wang J B. Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration[J]. Applied Mathematics and Computation, 2011, (217): 4819- 4826.
[11] Wu C Y, Sun S J, A sequencing problem in loading and unloading goods[J]. Operations Research Transactions, 2000, 4(4): 1-11.
[12] Song Z F, Sun S J, Wu C Y. A scheduling problem with earliness award and tardiness penalty[J]. Operations Research Transaction, 2002, 6(4): 31-36.
[13] Yu Y, Sun S J, Wang K, He L M. Tardiness penalty and earliness award with learnig effect processing time[J]. Operations Research Transaction, 2010, 14(2): 41-52.
[14] Yu Y, Lu Z, Sun S J, He L M, Hu J D. Scheduling problems on tardiness penalty and earliness award with simply linear processing time[J]. Journal of Shang Hai University(English Edition), 2009, 13(2): 123-128.
[15] Papadimitrion C H, Steiglitz K. Combinatorial optimization: algorithms and complexity[M]. Prentice-Hall, Englewood Gliffs, N J, 1982.
[16] Sengupta S, Algorithm and approximation schemes for minimum lateness/tardiness scheduling with rejection[J]. Lecture Notes in Computer Science, 2003, 2748: 79-90.

工件带简单线性恶化函数和共同交货期单机排序问题

Scheduling Simple Linear Deteriorating Jobs On a Single Machine with Common Due Date

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

[1]	刘春来, 王建军. 具有老化效应的单机共同工期安排和工件可拒绝排序问题[J]. 运筹与管理, 2021, 30(7): 66-70.
[2]	余英, 程明宝. 带学习效应和资源依赖的单机排序模型[J]. 运筹与管理, 2018, 27(1): 53-58.
[3]	刘春来, 王建军. 具有退化工件和老化效应的单机可拒绝排序问题[J]. 运筹与管理, 2017, 26(6): 95-101.
[4]	张新功, 严广乐, 唐国春, 唐海波. 具有指数和位置学习效应的机器排序问题[J]. 运筹与管理, 2011, 20(2): 97-101.