Unrelated parallel machine scheduling with job rejection and earliness-tardiness penalties
详细信息 查看官网全文
- 英文论文题名：Unrelated parallel machine scheduling with job rejection and earliness-tardiness penalties
- 论文作者：WU Rui ; GUO Shunsheng ; LI Xixing
- 英文论文作者：WU Rui ; GUO Shunsheng ; LI Xixing ; Hubei Digital Manufacturing Key Laboratory ; School of Mechanical and Electronic Engineering ; Wuhan University of Technology
- 年：2017
- 作者机构：Hubei Digital Manufacturing Key Laboratory,School of Mechanical and Electronic Engineering,Wuhan University of Technology;
- 英文论文关键词：Unrelated parallel machine scheduling ; Job rejection ; Earliness-tardiness penalties ; Genetic algorithm
- 会议召开时间：2017-07-26
- 会议录名称：第36届中国控制会议论文集（B）
- 英文会议录名称：Proceedings of the 36th Chinese Control Conference（B）
- 语种：英文
- 分类号：TP18
- 学会代码：KZLL
- 会议名称：第36届中国控制会议
- 会议地点：中国辽宁大连
- 主办单位：中国自动化学会控制理论专业委员会
- 学会名称：中国自动化学会控制理论专业委员会
- 页数：6
- 文件大小：338k
- 原文格式：D
- 会议级别：全国
摘要
In this paper, unrelated parallel machine scheduling problem with job rejection and earliness-tardiness penalties is investigated. The objective is to minimize the total penalty cost by deciding job acceptance, assigning jobs on unrelated machines,and determining the processing sequence of jobs on each machine. To solve this problem, a mixed integer programming(MIP)model is established, and a hybrid genetic algorithm which hybridizes Genetic Algorithm(GA) and tabu search(TS) with a concise encoding method, special genetic operators is proposed. Computational experiments are performed on three different sized sets of test instances which are randomly generated, and the results of comparative experiment demonstrate that the algorithm proposed in this paper can effectively solve the problem.
In this paper, unrelated parallel machine scheduling problem with job rejection and earliness-tardiness penalties is investigated. The objective is to minimize the total penalty cost by deciding job acceptance, assigning jobs on unrelated machines,and determining the processing sequence of jobs on each machine. To solve this problem, a mixed integer programming(MIP)model is established, and a hybrid genetic algorithm which hybridizes Genetic Algorithm(GA) and tabu search(TS) with a concise encoding method, special genetic operators is proposed. Computational experiments are performed on three different sized sets of test instances which are randomly generated, and the results of comparative experiment demonstrate that the algorithm proposed in this paper can effectively solve the problem.
In this paper, unrelated parallel machine scheduling problem with job rejection and earliness-tardiness penalties is investigated. The objective is to minimize the total penalty cost by deciding job acceptance, assigning jobs on unrelated machines,and determining the processing sequence of jobs on each machine. To solve this problem, a mixed integer programming(MIP)model is established, and a hybrid genetic algorithm which hybridizes Genetic Algorithm(GA) and tabu search(TS) with a concise encoding method, special genetic operators is proposed. Computational experiments are performed on three different sized sets of test instances which are randomly generated, and the results of comparative experiment demonstrate that the algorithm proposed in this paper can effectively solve the problem.
引文
[1]Sakib A Mondal and Anup K Sen.Single machine weighted earlinesstardiness penalty problem with a common due date.Computers&Operations Research,28(7):649-669,2001.
[2]K.R.Baker.Elements of sequencing and scheduling.Handbooks in Operations Research&Management Science,38(6):3035,1995.
[3]J.Bank and F.Werner.Heuristic algorithms for unrelated parallel machine scheduling with a common due date,release dates,and linear earliness and tardiness penalties.Mathematical&Computer Modelling,33(4-5):363-383,2001.
[4]Lingfa Lu and Liqi Zhang.Single-machine scheduling with production and rejection costs to minimize the maximum earliness.Journal of Combinatorial Optimization,pages 1-12,2016.
[5]Zhantao Li,Haidong Yang,Shaqing Zhang,and Guosheng Liu.Unrelated parallel machine scheduling problem with energy and tardiness cost.The International Journal of Advanced Manufacturing Technology,84(1):213-226,2016.
[6]Shih Wei Lin,Kuo Ching Ying,Yeni Chiang,and Wen Jie Wu.Minimising total weighted earliness and tardiness penalties on identical parallel machines using a fast ruin-andrecreate algorithm.International Journal of Production Research,54(22):1-12,2016.
[7]Hongyi Sun and Guoqing Wang.Parallel machine earliness and tardiness scheduling with proportional weights.Computers&Operations Research,30(5):801-808,2003.
[8]Safia Kedad-Sidhoum,Yasmin Rios Solis,and Francis Sourd.Lower bounds for the earlinesstardiness scheduling problem on parallel machines with distinct due dates.European Journal of Operational Research,189(3):1305-1316,2008.
[9]Jos A.Ventura and Daecheol Kim.Parallel machine scheduling with earlinesstardiness penalties and additional resource constraints.Computers&Operations Research,30(13):1945-1958,2003.
[10]Liu Min and Wu Cheng.Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems.Robotics and Computer-Integrated Manufacturing,22(4):279-287,2006.
[11]S Polyakovskiy and R M’Hallah.A multi-agent system for the weighted earliness tardiness parallel machine problem.Computers&Operations Research,44(3):115136,2014.
[12]Chen Yang Cheng and Lu Wei Huang.Minimizing total earliness and tardiness through unrelated parallel machine scheduling using distributed release time control.Journal of Manufacturing Systems,42:1-10,2017.
[13]Yang Tsai Chi and Chen Wang Yi.An improved mip-based approach to minimise total earliness and tardiness in unrelated parallel machines scheduling with machine idle time.International Journal of Manufacturing Technology&Management,29(5):271-287,2015.
[14]Mohammad Asghari and Samaneh Nezhadali.Fuzzy programming for parallel machines scheduling:Minimizing weighted tardiness/earliness and flowtime through genetic algorithm.Journal of Optimization in Industrial Engineering,2015.
[15]Adam Janiak,W Janiak,Adys,Mikhail Y Kovalyov,Erhan Kozan,and Erwin Pesch.Parallel machine scheduling and common due window assignment with job independent earliness and tardiness costs.Information Sciences,224(224):109-117,2013.
[16]Dar Li Yang,Hsin Tao Lee,and Suh Jenq Yang.Unrelated parallel-machine scheduling simultaneously with ratemodifying activities and earliness and tardiness penalties.Journal of the Chinese Institute of Industrial Engineers,29(4):282-289,2012.
[17]Wisut 1 Supithak.Memetic algorithm for non-identical parallel machines scheduling problem with earliness and tardiness penalties.International Journal of Manufacturing Technology&Management,22(1):26-38,2011.
[2]K.R.Baker.Elements of sequencing and scheduling.Handbooks in Operations Research&Management Science,38(6):3035,1995.
[3]J.Bank and F.Werner.Heuristic algorithms for unrelated parallel machine scheduling with a common due date,release dates,and linear earliness and tardiness penalties.Mathematical&Computer Modelling,33(4-5):363-383,2001.
[4]Lingfa Lu and Liqi Zhang.Single-machine scheduling with production and rejection costs to minimize the maximum earliness.Journal of Combinatorial Optimization,pages 1-12,2016.
[5]Zhantao Li,Haidong Yang,Shaqing Zhang,and Guosheng Liu.Unrelated parallel machine scheduling problem with energy and tardiness cost.The International Journal of Advanced Manufacturing Technology,84(1):213-226,2016.
[6]Shih Wei Lin,Kuo Ching Ying,Yeni Chiang,and Wen Jie Wu.Minimising total weighted earliness and tardiness penalties on identical parallel machines using a fast ruin-andrecreate algorithm.International Journal of Production Research,54(22):1-12,2016.
[7]Hongyi Sun and Guoqing Wang.Parallel machine earliness and tardiness scheduling with proportional weights.Computers&Operations Research,30(5):801-808,2003.
[8]Safia Kedad-Sidhoum,Yasmin Rios Solis,and Francis Sourd.Lower bounds for the earlinesstardiness scheduling problem on parallel machines with distinct due dates.European Journal of Operational Research,189(3):1305-1316,2008.
[9]Jos A.Ventura and Daecheol Kim.Parallel machine scheduling with earlinesstardiness penalties and additional resource constraints.Computers&Operations Research,30(13):1945-1958,2003.
[10]Liu Min and Wu Cheng.Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems.Robotics and Computer-Integrated Manufacturing,22(4):279-287,2006.
[11]S Polyakovskiy and R M’Hallah.A multi-agent system for the weighted earliness tardiness parallel machine problem.Computers&Operations Research,44(3):115136,2014.
[12]Chen Yang Cheng and Lu Wei Huang.Minimizing total earliness and tardiness through unrelated parallel machine scheduling using distributed release time control.Journal of Manufacturing Systems,42:1-10,2017.
[13]Yang Tsai Chi and Chen Wang Yi.An improved mip-based approach to minimise total earliness and tardiness in unrelated parallel machines scheduling with machine idle time.International Journal of Manufacturing Technology&Management,29(5):271-287,2015.
[14]Mohammad Asghari and Samaneh Nezhadali.Fuzzy programming for parallel machines scheduling:Minimizing weighted tardiness/earliness and flowtime through genetic algorithm.Journal of Optimization in Industrial Engineering,2015.
[15]Adam Janiak,W Janiak,Adys,Mikhail Y Kovalyov,Erhan Kozan,and Erwin Pesch.Parallel machine scheduling and common due window assignment with job independent earliness and tardiness costs.Information Sciences,224(224):109-117,2013.
[16]Dar Li Yang,Hsin Tao Lee,and Suh Jenq Yang.Unrelated parallel-machine scheduling simultaneously with ratemodifying activities and earliness and tardiness penalties.Journal of the Chinese Institute of Industrial Engineers,29(4):282-289,2012.
[17]Wisut 1 Supithak.Memetic algorithm for non-identical parallel machines scheduling problem with earliness and tardiness penalties.International Journal of Manufacturing Technology&Management,22(1):26-38,2011.