Order acceptance and scheduling on parallel machines with setup time and machine-eligibility constraints

WANG Bai-lin; LI Tie-ke; WANG Hai-feng

doi:10.13374/j.issn2095-9389.2019.04.014

Volume 41 Issue 4

Apr. 2019

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Engineering > 2019 > 41(4): 528-538

WANG Bai-lin, LI Tie-ke, WANG Hai-feng. Order acceptance and scheduling on parallel machines with setup time and machine-eligibility constraints[J]. Chinese Journal of Engineering, 2019, 41(4): 528-538. doi: 10.13374/j.issn2095-9389.2019.04.014

Citation:

WANG Bai-lin, LI Tie-ke, WANG Hai-feng. Order acceptance and scheduling on parallel machines with setup time and machine-eligibility constraints[J]. Chinese Journal of Engineering, 2019, 41(4): 528-538. doi: 10.13374/j.issn2095-9389.2019.04.014

Citation:

PDF( 531 KB)

Order acceptance and scheduling on parallel machines with setup time and machine-eligibility constraints

doi: 10.13374/j.issn2095-9389.2019.04.014

WANG Bai-lin^{1, 2
,
,},
LI Tie-ke^{1, 2},
WANG Hai-feng^{1, 2}

1.
Donlinks School of Economics and Management, University of Science and Technology Beijing, Beijing 100083, China
2.
Engineering Research Center of MES Technology for Iron & Steel Production, Ministry of Education, Beijing 100083, China

More Information

Corresponding author: WANG Bai-lin, E-mail: wangbl@ustb.edu.cn
Received Date: 2018-03-08
Publish Date: 2019-04-15

Abstract

Abstract

Integration of order acceptance and scheduling on unrelated parallel machines is a joint decision problem, and arise from the multi-variety customized production environment, which usually has the following characteristics. First, there are a number of parallel machines (production lines), each of which can only produce a limited variety of products referred as the machine-eligibility constraint. Second, the processing technologies of various machines differ; thus, these parallel machines are unrelated. Third, because the machines are unrelated, the setup time of an order is related not only to the order sequence but also to the machine used, which is called a sequence-and machine-dependent setup time. To minimize total cost, this study investigates the scheduling problems posed by order acceptance and unrelated parallel machines with setup time and machine-eligibility constraints. In this problem, an order has two options, rejection or acceptance. If an order is rejected, it generates a rejection cost. Otherwise, the order process must be completed before the due date, or there will be a tardiness cost. Therefore, the total cost spent is calculated as the sum of the total rejection cost of rejected orders and total weighted tardiness cost of accepted orders. To solve this problem, the effect of rejecting an order on the total cost was analyzed, and a list of rejecting methods and rejection rules were proposed. Furthermore, a cooperative coevolving genetic algorithm (CCGA) was developed. In this CCGA, an encoding scheme was proposed that divides chromosomes into two subsets corresponding to the order list and order assignment. Moreover, a list-rejecting-based decoding procedure was presented for deciding rejection for a chromosome. As the two subsets are independent of each other and their evolutionary constraints are essentially different, a cooperative coevolution strategy was applied to evolve the subpopulations of these subsets using partheno-genetic and traditional genetic operators. Computational experiments on a large set of randomly generated instances were performed to verify the effectiveness and efficiency of this algorithm. Additionally, the impacts of problem size and rejection cost were studied experimentally. The results reveal that in the majority of cases characterized by various problem sizes and rejection costs, the proposed algorithm performs effectively and efficiently.
- order acceptance and scheduling,
- unrelated parallel machines,
- setup time,
- machine-eligibility constraint,
- genetic algorithm,
- cooperative coevolution

FullText(HTML)

References(19)

References

[1]	Slotnick S A. Order acceptance and scheduling: a taxonomy and review. Eur J Oper Res, 2011, 212(1): 1 doi: 10.1016/j.ejor.2010.09.042
[2]	Shabtay D, Gaspar N, Kaspi M. A survey on offline scheduling with rejection. J Scheduling, 2013, 16(1): 3 doi: 10.1007/s10951-012-0303-z
[3]	Angel E, Bampis E, Kononov A.A FPTAS for approximating the unrelated parallel machines scheduling problem with costs//European Symposium on Algorithms.Berlin, 2001: 194
[4]	Hoogeveen H, Skutella M, Woeginger G J. Preemptive scheduling with rejection. Math Program, 2003, 94(2-3): 361 doi: 10.1007/s10107-002-0324-z
[5]	Sengupta S.Algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection//International Workshop on Algorithms and Data Structures.Ottawa, 2003: 79
[6]	Miao C X, Zhang Y Z, Wang C F.Bounded parallel-batch scheduling on unrelated parallel machines//International Conference on Algorithmic Applications in Management.Berlin, 2010: 220
[7]	Hsu C J, Chang C W. Unrelated parallel-machine scheduling with deteriorating jobs and rejection. Appl Mech Mater, 2012, 263- 266: 655 doi: 10.4028/www.scientific.net/AMM.263-266.655
[8]	Lin F, Zhang X Z, Cai Z X. Approximation algorithms for scheduling with rejection on two unrelated parallel machines. Int J Adv Comput Sci Appl, 2015, 6(11): 260 https://journals.indexcopernicus.com/search/article?icid=1185391
[9]	Jiang D K, Tan J Y. Scheduling with job rejection and nonsimultaneous machine available time on unrelated parallel machines. Theor Comput Sci, 2016, 616: 94 doi: 10.1016/j.tcs.2015.12.020
[10]	Joo C M, Kim B S. Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability. Comput Ind Eng, 2015, 85: 102 doi: 10.1016/j.cie.2015.02.029
[11]	Chen J S, Yang J S. Model formulations for the machine scheduling problem with limited waiting time constraints. J Inform Optimiz Sci, 2006, 27(1): 225 doi: 10.1080/02522667.2006.10699688
[12]	Vallada E, Ruiz R. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. Eur J Oper Res, 2011, 211(3): 612 doi: 10.1016/j.ejor.2011.01.011
[13]	鄔開俊, 魯懷偉. 采用并行協同進化遺傳算法的文本特征選擇. 系統工程理論與實踐, 2012, 32(10): 2215 https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201210014.htm Wu K J, Lu H W. PCEGA used to solve text feature selection. Syst Eng Theory Pract, 2012, 32(10): 2215 https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201210014.htm
[14]	Li X D, Yao X. Cooperatively coevolving particle swarms for large scale optimization. IEEE Trans Evol Comput, 2012, 16 (2): 210 doi: 10.1109/TEVC.2011.2112662
[15]	Pan Q K. An effective co-evolutionary artificial bee colony algorithm for steelmaking- continuous casting scheduling. Eur J Oper Res, 2016, 250(3): 702 doi: 10.1016/j.ejor.2015.10.007
[16]	(李茂軍, 童調生. 單親遺傳算法及其全局收斂性分析. 自動化學報, 1999, 25(1): 68) https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO901.009.htm Li M J, Tong T S. A partheno genetic algorithm and analysis on its global convergence. Acta Autom Sin, 1999, 25(1): 68 https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO901.009.htm
[17]	Wang J L, Huang W B, Ma G W, et al. An improved partheno genetic algorithm for multi-objective economic dispatch in cascaded hydropower systems. Int J Electr Power Energy Syst, 2015, 67: 591 doi: 10.1016/j.ijepes.2014.12.037
[18]	Zhu X, Li X P. Iterative search method for total flowtime minimization no-wait flowshop problem. Int J Mach Learn Cybern, 2015, 6(5): 747 doi: 10.1007/s13042-014-0312-7
[19]	Chen C L, Tzeng Y R, Chen C L. A new heuristic based on local best solution for permutation flow shop scheduling. Appl Soft Comput, 2015, 29: 75 doi: 10.1016/j.asoc.2014.12.011