Single machine scheduling with uncertain release times

详细信息    查看官网全文

• 英文论文题名：Single machine scheduling with uncertain release times
• 论文作者：Fan Yue ; Shiji Song ; Yuli Zhang ; Rui Wang
• 英文论文作者：Fan Yue ; Shiji Song ; Yuli Zhang ; Rui Wang ; Department of Automation ; Tsinghua University ; Systems Engineering Research Institute of Engineering Equipment ; Department of Industrial Engineering ; Tsinghua University ; Department of Basic ; Military Transportation University
• 年：2017
• 作者机构：Department of Automation,Tsinghua University;Systems Engineering Research Institute of Engineering Equipment;Department of Industrial Engineering,Tsinghua University;Department of Basic,Military Transportation University;
• 英文论文关键词：Roust scheduling ; Melton iron scheduling ; uncertain release timesConstraint generation algorithm
• 会议召开时间：2017-07-26
• 会议录名称：第36届中国控制会议论文集（B）
• 英文会议录名称：Proceedings of the 36th Chinese Control Conference（B）
• 语种：英文
• 分类号：TF758
• 学会代码：KZLL
• 会议名称：第36届中国控制会议
• 会议地点：中国辽宁大连
• 主办单位：中国自动化学会控制理论专业委员会
• 学会名称：中国自动化学会控制理论专业委员会
• 页数：6
• 文件大小：328k
• 原文格式：D
• 会议级别：全国

摘要

This paper establishes a robust optimization model and proposes constraint generation algorithm to solve a robust single machine scheduling problem with random release times. The performance criterion of interest is the maximum waiting time(MWT) over all jobs. Unlike the traditional stochastic programming model which requires exact distributions, our robust optimization model needs only the information of release time intervals. We formulate this uncertain optimization problem as a 0-1 linear programming model with a large number of constraints. To solve the model efficiently, a constraint generation algorithm(CGA) is proposed which generate constraint iteratively to obtain the optimal solution. The robustness of the optimal sequence under various probability distributions of release times is verified by simulation. Extensive computational experiments are implemented to demonstrate the effectiveness and efficiency of the proposed solution method.
This paper establishes a robust optimization model and proposes constraint generation algorithm to solve a robust single machine scheduling problem with random release times. The performance criterion of interest is the maximum waiting time(MWT) over all jobs. Unlike the traditional stochastic programming model which requires exact distributions, our robust optimization model needs only the information of release time intervals. We formulate this uncertain optimization problem as a 0-1 linear programming model with a large number of constraints. To solve the model efficiently, a constraint generation algorithm(CGA) is proposed which generate constraint iteratively to obtain the optimal solution. The robustness of the optimal sequence under various probability distributions of release times is verified by simulation. Extensive computational experiments are implemented to demonstrate the effectiveness and efficiency of the proposed solution method.

引文

[1]J.E.Everett,Iron ore production scheduling to improve product quality,inE uropean Journal of Operational Research,129(2):355C361,2001.
    [2]Mc Kay,N.Kenneth,F.R.Safayeni,and J.A.Buzacott,Jobshop scheduling theory:What is relevant?,in Interfaces,18(4):84C90,1988.
    [3]X.Cai,X.Wu,X.Zhou,More Stochastic Scheduling Models,in Optimal Stochastic Scheduling,347-394,2014.
    [4]D.Farias,R.Ismael,H.X.Zhao,and M.Zhao,A family of inequalities valid for the robust single machine scheduling polyhedron,inC omputers&Operations Research,37(9):1610C1614,2010.
    [5]Kouvelis,Panos,and G.Yu,Robust discrete optimization and its applications,in Springer Science&Business Media,Vol.14,2013.
    [6]Daniels,L.Richard,and P.Kouvelis,Robust scheduling to hedge against processing time uncertainty in single-stage production,in Management Science,41(2):363C376,1995.
    [7]Yang,Jian,and G.Yu,On the robust single machine scheduling problem,in Journal of Combinatorial Optimization,6(1):17C33,2002.
    [8]Kasperski,Adam,Minimizing maximal regret in the single machine sequencing problem with maximum lateness criterion,inO perations Research Letters,33(4):431C436,2005.
    [9]Aloulou,A.Mohamed Ali,and D.C.Federico,Complexity of single machine scheduling problems under scenario-based uncertainty,in Operations Research Letters,36(3):338C342,2008.
    [10]C.C.Lu,S.W.Lin,K.C.Ying,Robust scheduling on a single machine to minimize total flow time,in Computers&Operations Research,39(7):1682C1691,2012.
    [11]C.C.Lu,S.W.Lin,K.C.Ying,Minimizing worst-case regret of makespan on a single machine with uncertain processing and setup times,in Applied Soft Computing,23:144C151,2014.
    [12]Pinedo,L.Michael,Scheduling:Theory,Algorithms,and Systems,in Potts C.n.van Wassenhove L.n,2008.
    [13]Bagchi,Uttarayan,Simultaneous Minimization of Mean and Variation of Flow Time and Waiting Time in Single Machine Systems,in Operations Research,37(1):118C125,1989.
    [14]Umang,Nitish,A.L.Erera,and M.Bierlaire,The robust single machine scheduling problem with uncertain release and processing times,in Eprint Arxiv,2013.
    [15]G.Mcmahon,M.Florian,On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness[J],in Operations Research,23(3):475-482,1975.
    [16]Pinedo,L.Michael,Scheduling:Theory,Algorithms,and Systems,in Potts C.n.van Wassenhove L.n,2008.