| 一个批处理机随机E/ T 调度问题研究 |
| |
| 引用本文： | 张丽华,涂菶生. 一个批处理机随机E/ T 调度问题研究[J]. 系统工程理论与实践, 2005, 25(10): 114-119. DOI: 10.12011/1000-6788(2005)10-114 |
| |
| 作者姓名： | 张丽华 涂菶生 |
| |
| 作者单位： | 南开大学信息学院,天津,300071 |
| |
| 基金项目： | 国家自然科学基金(69674013)，国家攀登计划(970211017) |
| |
| 摘 要： | 对批处理机随机E/T(earliness and tardiness)调度问题,假设各批的加工时间独立同分布;各工件的交付期相互独立,并与加工时间独立;目标是极小化所有工件的提前与延迟时间和的均值.在加工时间和工件的交付期都服从指数分布的条件下,得到了最优调度的几个性质,基于这些性质用动态规划给出了一个求问题最优解的算法,此算法的时间复杂度为O(n2B2)(B
|
| 关 键 词： | 调度问题 批处理机调度问题 随机调度 E/T调度 动态规划 |
| 文章编号： | 1000-6788(2005)10-0114-06 |
| 修稿时间： | 2004-09-30 |
An Earliness and Tardiness Stochastic Scheduling Problem on a Batch Processor |
| |
| ZHANG Li-hua,TU Feng-sheng. An Earliness and Tardiness Stochastic Scheduling Problem on a Batch Processor[J]. Systems Engineering —Theory & Practice, 2005, 25(10): 114-119. DOI: 10.12011/1000-6788(2005)10-114 |
| |
| Authors: | ZHANG Li-hua TU Feng-sheng |
| |
| Abstract: | To an earliness and tardiness stochastic scheduling problem on a batch processor,let processing time of various batches be i.i.d(independent identical distributed);the due dates of various jobs be independent,and independent with the processing time of various batches;the objective is to minimize the expected total earliness and tardiness of jobs.When processing times and due dates are random variables exponentially distributed with known rates,several properties of the optimal schedule are found;based on these properties,an algorithm using dynamic programming to find the optimal solution is proposed,the time complexity of the algorithm is O(n~2B~2)(B
|
| |
| Keywords: | scheduling problem batch processor scheduling problem stochastic scheduling E/T scheduling dynamic programming |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
|
点击此处可从《系统工程理论与实践》下载全文 |
