基于三个影响因子的单机排序问题.docVIP

基于三个影响因子的单机排序问题 田桂鑫 曲光夫 兰州大学数学与统计学院，兰州市　 730000 摘要：本文考虑基于退化、指数学习效应和开始时间三个影响因子的单机排序问题，也就是说 工件的实际加工时间不仅与之前加工的工件有关，而且与所处的工件加工位置和开始加工时间 有关系。这篇文章给出一个新的模型，并且证明单机排序问题的最小化时间表长、最小化总完 工时间及最小化所有工件完工时间的平方和问题能根据 SPT 规则（最短加工时间优先规则） 得到最优解。并且证明在给定的条件下，最小化最大延误和最小化加权总完工时间问题能得到 最优解。 关键词：单机排序，退化，指数学习效应，开始加工时间 中图分类号： O224,O231 Single-machine scheduling with three in?uencing factors for job processing time TIAN Gui-Xin QU Guang-Fu School of Mathematics and Statistics, Lanzhou University, Lanzhou 730000 Abstract: This paper considers the single machine scheduling problems with time-dependent deterioration and exponential learning e?ect and the starting time, i.e. the actual processing time of a job depends not only on the processing time of the jobs already processed but also on its scheduled position and its starting time. Here considers a new model and shows that the single machine scheduling problems to minimize the makespan and the total completion time and the sum of the 2th power of job completion times can be solved by the smallest(normal) processing time ?rst (SPT) rule respectively. It can be proved that the total weighted completion time minimization problem and the maximum lateness minimization problem are polynomially solvable under certain conditions. Key words: single machine scheduling, deterioration, exponential learning e?ect, starting time 0 Introduction In classical scheduling theory, job processing times are supposed to be ?xed and constant values. In practice,however, there are many situations that the processing times of jobs may 基金项目： 作者简介： Tian Gui-Xin（1986-），female，major research direction：Institute of Operations Research and Control Theory. Qu Guang-Fu (1988-) , male, major research direction：Computational Mathematics. -1- be subject to change due to deterioration and starting time and learning phenomena. In many real-life scheduling setting a job processed later consumes more time than when it is processed earlier, this phenomenon is known as scheduling wit