非对称模糊加工时间工期指派调度优化问题的一类多项式求解算法
|
摘要
针对工件加工时间为非对称模糊数,极小化提前完工惩罚和拖期完工惩罚之和的均值的单机工期指派调度优化问题(1|p|∑nM(e_iE_i+t_iT_i))展开研究.证明了当模糊加工时间具有相同宽度比时,该问题是多项式可解的,并给出了多项式求解算法.同时根据历史数据,构造了工期指派问题的调度模型,并利用所给出的算法求得最优解,从而表明所提出的模型和算法的有效性.
A single machine due date assignment scheduling problem with asymmetric fuzzy processing is investigated,to minimize the total earliness and tardiness penalties,written as (1|p|∑nM(e_iE_i+t_iT_i)),Further,it is proven to be polynomially solvable when the processing times have the same width ratio.A numerical example is shown to illustrate that the proposed method is effective based on the due date assignment scheduling problems with historical data of processing time.
A single machine due date assignment scheduling problem with asymmetric fuzzy processing is investigated,to minimize the total earliness and tardiness penalties,written as (1|p|∑nM(e_iE_i+t_iT_i)),Further,it is proven to be polynomially solvable when the processing times have the same width ratio.A numerical example is shown to illustrate that the proposed method is effective based on the due date assignment scheduling problems with historical data of processing time.
引文
[1]Hino C M,Ronconi D P,Mendes A B.Minimizing earliness and tardiness penalties in a single-machine problem with a common due date[J].European Journal of Operational Research,2005,160(1):190
[2]Bauman J,Józefowska J.Minimizing the earlinesstardiness costs on a single machine[J].Computers&Operations Research,2006,33(11):3219
[3]Janiak A,Kwiatkowski T,Lichtenstein M.Scheduling problems with a common due window assignment:a survey[J].International Journal of Applied Mathematics and Computer Science,2013,23(1):231
[4]Shabtay D,Steiner G.Two due date assignment problems in scheduling a single machine[J].Operations Research Letters,2006,34(6):683
[5]Baykasoˇglu A,G9cken M,Unutmaz Z D.New approaches to due date assignment in job shops[J].European Journal of Operational Research,2008,187(1):31
[6]Zhao C,Hsu C,Cheng S,et al.Due date assignment and single machine scheduling with deteriorating jobs to minimize the weighted number of tardy jobs[J].Applied Mathematicsand Computation,2014,248:503
[7]Cheng T C E,Gupta M C.Survey of scheduling research involving due date determination decisions[J].European Journal of Operational Research,1989,38(2):156
[8]Seidmann A,Panwalker S S,Smith M L.Optimal assignment of due-dates for a single processor scheduling problem[J].International Journal of Production Research,1981,19(4):393
[9]Panwalker S S,Smith M L,Seidmann A.Common due date assignment to minimize total penalty for the one machine scheduling problem[J].Operations Research,1982,30(2):391
[10]Gordon V,Proth J M,Chu C.A survey of the state-ofthe-art of common due date assignment and scheduling research[J].European Journal of Operational Research,2002,139(1):1
[11]Cheng T C E.Optimal due-date assignment for a single machine sequencing problem with random processing times[J].International Journal of Systems Science,1986,17(8):1139
[12]Cheng T C E.Optimal assignment of slack due-dates and sequencing of jobs with random processing times on a single machine[J].European Journal of Operational Research,1991,51(3):348
[13]Soroush H M.Sequencing and due-date determination in the stochastic single machine problem with earliness and tardiness costs[J].European Journal of Operations Research,1999,113(2):450
[14]Portougal V,Trietsch D.Setting due dates in a stochastic single machine environment[J].Computers&Operations Research,2006,33(6):1681
[15]Baker K R.Minimizing earliness and tardiness costs in stochastic scheduling[J].European Journal of Operational Research,2014,236(2):445
[16]Iranpoor M,Fatemi Ghomi S M T,Zandieh M.Due-date assignment and machine scheduling in a low machinerate situation with stochastic processing times[J].Computers&Operations Research,2013,40(4):1100
[17]Xia Y,Chen B,Yue J.Job sequencing and due date assignment in a single machine shop with uncertain processing times[J].European Journal of Operational Research,2008,184(1):63
[18]Li J,Sun K,Xu D,et al.Single machine due date assignment scheduling problem with customer service level in fuzzy environment[J].Applied Soft Computing,2010,10(3):849
[19]Li J,Yuan X,Lee E S,et al.Setting due dates to minimize the total weighted possibilistic mean value of the weighted earliness/tardiness costs on a single machine[J].Computers and Mathematics with Applications,2011,62(11):4126
[20]Zadeh L A.Fuzzy sets[J].Information and Control,1965,8(3):338
[21]Hanss M.Applied fuzzy arithmetic:an introduction with engineering applications[M].Berlin:Springer,2005
[22]Carlsson C,Fullér R.On possibilistic mean value and variance of fuzzy numbers[J].Fuzzy Sets and Systems,2001,122(2):315
[2]Bauman J,Józefowska J.Minimizing the earlinesstardiness costs on a single machine[J].Computers&Operations Research,2006,33(11):3219
[3]Janiak A,Kwiatkowski T,Lichtenstein M.Scheduling problems with a common due window assignment:a survey[J].International Journal of Applied Mathematics and Computer Science,2013,23(1):231
[4]Shabtay D,Steiner G.Two due date assignment problems in scheduling a single machine[J].Operations Research Letters,2006,34(6):683
[5]Baykasoˇglu A,G9cken M,Unutmaz Z D.New approaches to due date assignment in job shops[J].European Journal of Operational Research,2008,187(1):31
[6]Zhao C,Hsu C,Cheng S,et al.Due date assignment and single machine scheduling with deteriorating jobs to minimize the weighted number of tardy jobs[J].Applied Mathematicsand Computation,2014,248:503
[7]Cheng T C E,Gupta M C.Survey of scheduling research involving due date determination decisions[J].European Journal of Operational Research,1989,38(2):156
[8]Seidmann A,Panwalker S S,Smith M L.Optimal assignment of due-dates for a single processor scheduling problem[J].International Journal of Production Research,1981,19(4):393
[9]Panwalker S S,Smith M L,Seidmann A.Common due date assignment to minimize total penalty for the one machine scheduling problem[J].Operations Research,1982,30(2):391
[10]Gordon V,Proth J M,Chu C.A survey of the state-ofthe-art of common due date assignment and scheduling research[J].European Journal of Operational Research,2002,139(1):1
[11]Cheng T C E.Optimal due-date assignment for a single machine sequencing problem with random processing times[J].International Journal of Systems Science,1986,17(8):1139
[12]Cheng T C E.Optimal assignment of slack due-dates and sequencing of jobs with random processing times on a single machine[J].European Journal of Operational Research,1991,51(3):348
[13]Soroush H M.Sequencing and due-date determination in the stochastic single machine problem with earliness and tardiness costs[J].European Journal of Operations Research,1999,113(2):450
[14]Portougal V,Trietsch D.Setting due dates in a stochastic single machine environment[J].Computers&Operations Research,2006,33(6):1681
[15]Baker K R.Minimizing earliness and tardiness costs in stochastic scheduling[J].European Journal of Operational Research,2014,236(2):445
[16]Iranpoor M,Fatemi Ghomi S M T,Zandieh M.Due-date assignment and machine scheduling in a low machinerate situation with stochastic processing times[J].Computers&Operations Research,2013,40(4):1100
[17]Xia Y,Chen B,Yue J.Job sequencing and due date assignment in a single machine shop with uncertain processing times[J].European Journal of Operational Research,2008,184(1):63
[18]Li J,Sun K,Xu D,et al.Single machine due date assignment scheduling problem with customer service level in fuzzy environment[J].Applied Soft Computing,2010,10(3):849
[19]Li J,Yuan X,Lee E S,et al.Setting due dates to minimize the total weighted possibilistic mean value of the weighted earliness/tardiness costs on a single machine[J].Computers and Mathematics with Applications,2011,62(11):4126
[20]Zadeh L A.Fuzzy sets[J].Information and Control,1965,8(3):338
[21]Hanss M.Applied fuzzy arithmetic:an introduction with engineering applications[M].Berlin:Springer,2005
[22]Carlsson C,Fullér R.On possibilistic mean value and variance of fuzzy numbers[J].Fuzzy Sets and Systems,2001,122(2):315