An Efficient Bi-objective Genetic Algorithm for the Single Batch-Processing Machine Scheduling Problem with Sequence Dependent Family Setup Time and Non-identical Job Sizes
Subject Areas : Business and Marketing
Javad
Rezaeian
1
(Department of industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran)
Yaser
Zarook
2
(Department of Industrial Engineering, Mazandaran University of Science and Technology)
Keywords: Release Date, Batch Processing, Incompatible Job Family, Split Job Size, Family Setup Time,
Abstract :
This paper considers the problem of minimizing make-span and maximum tardiness simultaneously for scheduling jobs under non-identical job sizes, dynamic job arrivals, incompatible job families,and sequence-dependentfamily setup time on the single batch- processor, where split size of jobs is allowed between batches. At first, a new Mixed Integer Linear Programming (MILP) model is proposed for this problem; then, it is solved by -constraint method.Since this problem is NP-hard, a bi-objective genetic algorithm (BOGA) is offered for real-sized problems. The efficiency of the proposed BOGA is evaluated to be comparedwith many test problemsby -constraint method based on performance measures. The results show that the proposed BOGAis found to be more efficient and faster than the -constraint method in generating Pareto fronts in most cases.
Arabani, A., Zandieh, M., and Fatemi Ghomi, S. M. T. (2011). Multi-objective genetic-based algorithms for a cross-docking scheduling problem. Applied Soft Computing, 11(8), 4954-4970.
Baker, R. (1943). Principles of sequencing and scheduling. Wiley, New Jersey.
Cheng, B. , Wang, Q., Yang, Sh., and Hu, X. (2013).An improved ant colony optimization for scheduling identical parallel batching machines with arbitrary job sizes. Applied Soft Computing, 13(2), 765-772.
Crauwels, H. A. J., and Potts, C. N. (1996). Local search heuristics for single-machine scheduling with batching to minimize the number of late jobs. European Journal of Operational Research, 90(2), 200-213.
Damodaran, P., Manjeshwar, P. K., and Srihari, K. (2006). Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms. International Journal of Production Economics, 103(2), 882–891.
Dauzère-Pérès, S., and Mönch, L. (2013). Scheduling jobs on a single batch processing machine with incompatible job families and weighted number of tardy jobs objective. Computers& Operations Research, 40(5), 1224-1233.
Deb, K., Agrawal, S., Pratap, A., Meyarivan, T. (2002). A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II. Lecture notes in computer science 1917 (2000): 849-858.
Dupont, L., and Dhaenens, C. (2002). Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure. Computers & Operations Research, 29(7), 807-819.
Favuzza, S., Ippolito, M. G., Riva Sanseverino, E. (2006). Crowded comparison operators for constraints handling in NSGA-II for optimal design of the compensation system in electrical distribution networks. Advanced Engineering Informatics, 20(2), 201–211.
Gendreau, M. (2009). An exact -constraint method for bi objective combinatorial optimization problems. European Journal of Operational Research, 194(1), 39-50.
Guo, Z. X., Wong, W. K., and Leung, S. Y. S. (2013). A hybrid intelligentmodel for order allocation planning in make-to-order manufacturing.Applied Soft Computing, 13(3), 1376-1390.
Hui, Lu., Ruiyao,Niu., Jing, Liu., Zheng, Zhu. (2013). A chaotic non-dominated sorting genetic algorithm for the multi-objective automatic test task scheduling problem. Applied Soft Computing, 13(5), 2790-2802.
HusseinzadehKashan, A., Karimi, B., and Jolai, F. (2010). An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes. Engineering Applications of Artificial Intelligence, 23(6), 911–922.
Husseinzadeh Kashan, A. , Karimi, B., and Jenabi, M. (2008). A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes. Computers & Operations Research, 35(4), 1084–1098.
Knowles, J., L. Thiele, E. Zitzler. (2006). A tutorial on the performance assessment of stochastic multiobjective optimizers. Technical Report 214, Computer Engineering and Networks Laboratory (TIK), ETH Zurich. [Revised version.]
Koh, Sh., Koo, P. H., Kim, D. Ch., and Hur, W. Su. (2005). Scheduling a single batch processing machine with arbitrary job sizes and incompatible job families. International Journal of Production Economics, 98(1), 81–96.
Liu, L. L., Ng, C. T., and Chen, T. C. E. (2009). Bi-criterion scheduling with equal processing times on a batch processing machine. Computers & Operations Research, 36(2), 110–118.
Malvea, S., and Uzsoy, R. (2007). A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families. Computers & Operations Research, 34(10), 3016 – 3028.
Mavrotas, G. (2009). Effective implementation of the -constraint method in multi objective mathematical programming problems. Applied Mathematics and Computation, 213(2), 455-465.
Melouk, Sh., Damodaran, P., and Chang, P. Y. (2004). Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. International Journal of Production Economics, 87(2), 141–147.
Minella et al. (2008). A Review and Evaluation of Multi-objective Algorithms for the Flow-shop Scheduling Problem, Journal on Computing, 20(3),451-471.
Paquete, L. F. (2005). Stochastic local search algorithms for multi-objective combinatorial optimization: Method and analysis. Ph.D.thesis, Computer Science Department, Darmstadt Universityof Technology, Darmstadt, Germany.
Perez, I., Fowler, W., and Matthew, W. (2005). Minimizing total weighted tardiness on a single batch process machine with incompatible job families. Computers & Operations Research, 32(2), 327–341.
Pinedo, M. L. (2008). Scheduling Theory, algorithms, and systems. 3ed, Springer, New York.
Rafiee, N., Karimi, B., and HusseinzadehKashan, A. (2010). A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes. Computers & Operations Research, 37(10), 1720–1730.
Rezaeian, J., Javadian, N., Tavakkoli-Moghaddam, R., and Jolai F. (2013). A hybrid multi-objective approach based on the genetic algorithm and neural network to design an incremental cellular manufacturing system. Computers & Industrial Engineering, 66(4), 1004-1014.
Rui, X., Huaping, Ch., and Xueping, Li. (2012). Makespan minimization on single batch-processing machine via ant colony optimization. Computers & Operations Research, 39(3), 582–593.
Sung, C. S., Choung, Y. I., Hong, J. M., and Kim, Y. H. (2002). Minimizing makespan on a single burn-in oven with job families and dynamic job arrivals. Computers & Operations Research, 29(8), 995-1007.
Wang, Ch. Sh., and Uzsoy, R. (2002). A genetic algorithm to minimize maximum lateness on a batch processing machine. Computers & Operations Research, 29(12), 1621-1640.
Xu, R., Chen, H., and Li, X. (2013). A bi-objective scheduling problem on batch machines via a Pareto-based ant colony system. International Journal of Production Economics, 145(1), 371-386.
Yao, Sh., and Jiang, Z. (2012). A branch and bound algorithm for minimizing total completion time on a single batch machine with incompatible job families and dynamic arrivals. Computers & Operations Research, 39(5), 939–951.
Zitzler, E., L. Thiele, M. Laumanns, C. M. Fonseca, V. G. da Fonseca. (2003). Performance assessment of multi-objective optimizers:An analysis and review. IEEE Trans. Evolutionary Comput. (7) 117–132.