文献类型：期刊文献

中文题名：单台机器E-T随机排序问题的多项式算法

英文题名：A Polynomial Algorithm for Stochastic Scheduling Problem on Single Machine with Earliness and Tardiness Penalties

作者：顾满占[1];鲁习文[1]

机构：[1]华东理工大学理学院数学系,上海200237

年份：2008

卷号：17

期号：5

起止页码：64

中文期刊名：运筹与管理

外文期刊名：Operations Research and Management Science

收录：CSTPCD;;国家哲学社会科学学术期刊数据库;CSCD:【CSCD_E2011_2012】；

基金：国家自然科学基金资助项目(10771067);教育部回国人员科研启动基金资助项目;华东理工大学理学院校科研基金资助项目

语种：中文

中文关键词：随机排序;贪婪算法;E—T问题;多项式算法

外文关键词：stochastic scheduling; greedy algorithm; E-T scheduling; polynomial algorithm

摘要：本文研究排序问题中的E-T问题,工件在单台机器上加工,n个工件的加工时间都为整数p,相同的工期d为离散分布,满足∑mi=1P(d=ξi)=1,其中ξi为整数,目标是使E(∑(Ej+Tj))的期望值最小。应用贪婪算法和二分法思想,我们提出解决该问题的一个最优算法,并得出该算法的复杂性为O(nmlogp)。
In this paper, the one-machine scheduling with earliness and tardiness is considered. There are n jobs to be processed, and the processing time of all jobs is identical, which is integer. In addition, the jobs＇common due date is a stochastic variable satisfying∑i=1^mP（d=ξi）=1 and ξi is integer. The objective is to minimize the expected value of total cost of earliness and tardiness, which could be denoted as E（∑（Ei＋Tj））.In order tosolve this problem, a method consisting of greedy algorithm and binary skill is implemented. Moreover, the algorithm analysis reveals the method is polynomial, and the time complexity is O（nmlogp）.