New Formulation and Solution in PCB Assembly Systems with Parallel Batch processors

Document Type : Research Paper

Authors

1 phd student, Department of Industrial Engineering, College of Technology, Mazandaran University of Science & Technology, Babol,

2 Assistant Professor, Department of Industrial Engineering, Faculty of Engineering, shahed University

Abstract

This paper considers the scheduling problem of parallel batch processing machines with non-identical job size and processing time. In this paper, a new mathematical model with ready time and batch size constraints is presented to formulate the problem mathematically, in which simultaneous reduction of the makespan and earliness-tardiness is the objective function. In recent years, the nature-inspired computational intelligent algorithms have been successfully employed to achieve the optimum design of different structures. Since the proposed model is NP-hard, a metaheuristic algorithm according to a harmony search algorithm is developed and analyzed for solving the batch processing machine scheduling problem addressed in the current paper. Various parameters and operators of the proposed harmony search algorithm are discussed and calibrated by means of the Taguchi statistical technique. In order to evaluate the proposed algorithm, instance problems in concordance with previous research are generated. The proposed algorithm and basic harmony search, improved harmony search and global best harmony search are solved and the results of all the algorithms are compared. The conclusion reveals that the proposed algorithm performs better than the other algorithms.
 

Keywords

References

Bank, Jan, & Werner, Frank. (2001). Heuristic algorithms for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties. Mathematical and Computer Modelling, 33(4), 363-383.
Cakici, Eray, Mason, Scott J, Fowler, John W, & Geismar, H Neil. (2013). Batch scheduling on parallel machines with dynamic job arrivals and incompatible job families. International Journal of Production Research, 51(8), 2462-2477.
Chan, Felix TS, Bhagwat, Rajat, & Wadhwa, S. (2007). Flexibility performance: Taguchi's method study of physical system and operating control parameters of FMS. Robotics and Computer-Integrated Manufacturing, 23(1), 25-37.
Chang, P-Y, Damodaran*, P, & Melouk, S. (2004). Minimizing makespan on parallel batch processing machines. International
Journal of Production Research, 42 (19), 4211-4220.
Cheng, Bayi, Wang, Qi, Yang, Shanlin, & Hu, Xiaoxuan. (2013). An improved ant colony optimization for scheduling identical parallel batching machines with arbitrary job sizes. Applied Soft Computing, 13(2), 765-772.
Cheng, Bor-Wen, & Chang, Chun-Lang. (2007). A study on flowshop scheduling problem combining Taguchi experimental design and genetic algorithm. Expert Systems with Applications, 32(2), 415-421.
Chung, SH, Tai, YT, & Pearn, WL. (2009). Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes. International Journal of Production Research, 47(18), 5109-5128.
Damodaran, Purushothaman, Diyadawagamage, Don Asanka, Ghrayeb, Omar, & Vélez-Gallego, Mario C. (2012). A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines.
 The International Journal of Advanced Manufacturing Technology, 58 (9-12), 1131-1140.
Damodaran, Purushothaman, Hirani, Neal S, & Velez-Gallego, Mario C. (2009). Scheduling identical parallel batch processing machines to minimise makespan using genetic algorithms. European Journal of Industrial Engineering, 3(2), 187-206.
Damodaran, Purushothaman, & Velez-Gallego, Mario C. (2010). Heuristics for makespan minimization on parallel batch processing machines with unequal job ready times. The International Journal of Advanced Manufacturing Technology, 49(9-12), 1119-1128.
Damodaran, Purushothaman, Vélez-Gallego, Mario C, & Maya, Jairo. (2011). A GRASP approach for makespan minimization on parallel batch processing machines. Journal of Intelligent Manufacturing, 22(5), 767-777.
Feng, Qi, Yuan, Jinjiang, Liu, Hailing, & He, Cheng. (2013). A note on two-agent scheduling on an unbounded parallel-batching machine with makespan and maximum lateness objectives. Applied Mathematical Modelling, 37(10), 7071-7076.
Geem, Zong Woo, Kim, Joong Hoon, & Loganathan, GV. (2001). A new heuristic optimization algorithm: harmony search.
Simulation, 76 (2), 60-68.
Jia, Zhao-hong, & Leung, Joseph Y-T. (2015). A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes. European Journal of Operational Research, 240(3), 649-665.
Kashan, Ali Husseinzadeh, Karimi, Behrooz, & Jenabi, Masoud. (2008). A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes. Computers & Operations Research, 35(4), 1084-1098.
Kedad-Sidhoum, Safia, Solis, Yasmin Rios, & Sourd, Francis. (2008). Lower bounds for the earliness–tardiness scheduling problem on parallel machines with distinct due dates. European Journal of Operational Research, 189(3), 1305-1316.
Lee, C-Y. (1999). Minimizing makespan on a single batch processing machine with dynamic job arrivals. International Journal of
Production Research, 37 (1), 219-236.
Lee, Kang Seok, Geem, Zong Woo, Lee, Sang-ho, & Bae, Kyu-woong. (2005). The harmony search heuristic algorithm for discrete structural optimization. Engineering Optimization, 37(7), 663-684.
Li, XiaoLin, Huang, YanLi, Tan, Qi, & Chen, HuaPing. (2013). Scheduling unrelated parallel batch processing machines with nonidentical job sizes. Computers & Operations Research, 40(12), 2983-2990.
Mahdavi, M, Fesanghary, Mohammad, & Damangir, E. (2007). An improved harmony search algorithm for solving optimization problems. Applied mathematics and computation, 188(2), 1567-1579.
Mönch, Lars, & Unbehaun, Robert. (2007). Decomposition heuristics for minimizing earliness–tardiness on parallel burn-in ovens with a common due date. Computers & operations research, 34(11), 3380-3396.
Montgomery, Douglas C. (2012). Design and analysis of experiments (Vol. 7).
Moslehi, G, Mirzaee, M, Vasei, M, Modarres, M, & Azaron, A. (2009). Two-machine flow shop scheduling to minimize the sum of maximum earliness and tardiness. International Journal of Production Economics, 122(2), 763-773.
Naderi, B, Ghomi, SMT, & Aminnayeri, M. (2010). A high performing metaheuristic for job shop scheduling with sequencedependent setup times. Applied Soft Computing, 10(3), 703-710.
Naderi, B, Zandieh, M, & Roshanaei, V. (2009). Scheduling hybrid flowshops with sequence dependent setup times to minimize makespan and maximum tardiness. The International Journal of Advanced Manufacturing Technology, 41(11-12), 1186-1198.
Omran, Mahamed GH, & Mahdavi, Mehrdad. (2008). Global-best harmony search. Applied Mathematics and Computation, 198(2),
643-656.
Pan, Quan-Ke, Suganthan, PN, Liang, JJ, & Tasgetiren, M Fatih. (2010). A local-best harmony search algorithm with dynamic subpopulations. Engineering Optimization, 42(2), 101-117.
Pan, Quan-Ke, Suganthan, Ponnuthurai N, Tasgetiren, M Fatih, & Liang, Jing J. (2010). A self-adaptive global best harmony search algorithm for continuous optimization problems. Applied Mathematics and Computation, 216(3), 830-848.
Pinedo, Michael. (2012).Scheduling: theory, algorithms, and systems: Springer.
Ruiz, Rubén, & Maroto, Concepción. (2006). A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. European Journal of Operational Research, 169(3), 781-800.
Sahraeian, R, Samaei, F, & Rastgar, I. (2014). Minimizing the makespan on parallel batch scheduling with stochastic times Annals of Industrial Engineering 2012 (pp. 209-216): Springer.
Shao, Hao, Chen, Hua-Ping, Huang, George Q, Xu, Rui, Cheng, Ba-yi, Wang, Shuan-shi, & Liu, Bo-wen. (2008). 
Minimizing makespan for parallel batch processing machines with non-identical job sizes using neural nets approach.
Paper presented at the Industrial Electronics and Applications, 2008. ICIEA 2008. 3rd IEEE Conference on.Taherinejad, Nima. (2009). Highly reliable harmony search algorithm. Paper presented at the Circuit Theory and Design, 2009.ECCTD 2009. European Conference on.
Toksarı, M Duran, & Güner, Ertan. (2009). Parallel machine earliness/tardiness scheduling problem under the effects of position based learning and linear/nonlinear deterioration. Computers & Operations Research, 36(8), 2394-2417.
Velez Gallego, Mario Cesar, & Adviser-Damodaran, Purushothaman. (2009). Algorithms for scheduling parallel batch processing machines with non-identical job ready times.
Wang, Hui-Mei, & Chou, Fuh-Der. (2010). Solving the parallel batch-processing machines with different release times, job sizes, and capacity limits by metaheuristics. Expert Systems with Applications, 37(2), 1510-1521.
Wang, Jun-Qiang, & Leung, Joseph Y-T. (2014). Scheduling jobs with equal-processing-time on parallel machines with nonidentical capacities to minimize makespan. International Journal of Production Economics, 156, 325-331.
Xu, Shubin, & Bean, James C. (2007). A genetic algorithm for scheduling parallel non-identical batch processing machines. Paper presented at the Computational Intelligence in Scheduling, 2007. SCIS'07. IEEE Symposium on.
Xu, Shubin, & Bean, James C. (2015). Scheduling parallel-machine batch operations to maximize on-time delivery performance. Journal of Scheduling, 1-18.
Yilmaz Eroglu, Duygu, Ozmutlu, H Cenk, & Ozmutlu, Seda. (2014). Genetic algorithm with local search for the unrelated parallel machine scheduling problem with sequence-dependent set-up times. International Journal of Production Research, 52(19), 5841-
5856.
Zou, Dexuan, Gao, Liqun, Li, Steven, & Wu, Jianhua. (2011). Solving 0–1 knapsack problem by a novel global harmony search algorithm. Applied Soft Computing, 11(2), 1556-1564.

Files

Share

How to cite

Statistics