Group-shop scheduling with sequence-dependent set-up and transportation times. (English) Zbl 1428.90066
Summary: This paper considers a group-shop scheduling problem (GSSP) with sequence-dependent set-up times (SDSTs) and transportation times. The GSSP provides a general formulation including the job-shop and the open-shop scheduling problems. The consideration of set-up and transportation times is among the most realistic assumptions made in the field of scheduling. In this paper, we study the GSSP with transportation and anticipatory SDSTs, where jobs are released at different times and there are several transporters to carry jobs. The objective is to find a job schedule that minimizes the makespan, that is, the time at which all jobs are completed and transported to the warehouse (or to the customer). The problem is formulated as a disjunctive programming problem and then prepared in a form of mixed integer linear programming (MILP). Due to the non-deterministic polynomial-time hardness (NP-hardness) of the GSSP, large instances cannot be optimally solved in a reasonable amount of time. Therefore, a genetic algorithm (GA) hybridized with an active schedule generator is proposed to tackle large-sized instances. Both Baldwinian and Lamarckian versions of the proposed hybrid algorithm are then implemented and evaluated through computational experiments.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
group-shop scheduling; sequence-dependent set-up times; transportation times; makespan; genetic algorithmReferences:
| [1] | Allahverdi, A.; Soroush, H. M., The significance of reducing setup times/setup costs, Eur. J. Oper. Res., 187, 978-984 (2008) · Zbl 1137.90475 |
| [2] | Allahverdi, A.; Ng, C. T.; Cheng, T. C.E.; Kovalyov, M. K., A survey of scheduling problems with setup times or costs, Eur. J. Oper. Res., 187, 985-1032 (2008) · Zbl 1137.90474 |
| [3] | Pinedo, M., Scheduling: Theory, Algorithms, and Systems (2008), Springer: Springer New York · Zbl 1155.90008 |
| [4] | Baker, K. R.; Trietsch, D., Principles of Sequencing and Scheduling (2009), John Wiley & Sons: John Wiley & Sons New Jersey · Zbl 1169.90009 |
| [5] | Naderi, B.; Zandieh, M.; Shirazi, M. A.H. A., Modeling and scheduling a case of flexible flowshops: total weighted tardiness minimization, Comput. Ind. Eng., 57, 1258-1267 (2009) |
| [6] | Sule, D. R., Industrial Scheduling (1996), PWS Publishing Company: PWS Publishing Company USA |
| [8] | Blum, C.; Sampels, M., An ant colony optimization algorithm for shop scheduling problems, J. Math. Model. Algorithms, 3, 285-308 (2004) · Zbl 1146.90405 |
| [9] | Liu, S. Q.; Ong, H. L.; Ng, K. M., A fast tabu search algorithm for the group shop scheduling problem, Adv. Eng. Software, 36, 533-539 (2005) · Zbl 1101.68422 |
| [10] | Ahmadizar, F.; Ghazanfari, M.; Fatemi Ghomi, S. M.T., Application of chance-constrained programming for stochastic group shop scheduling problem, Int. J. Adv. Manuf. Technol., 42, 321-334 (2009) |
| [11] | Ahmadizar, F.; Ghazanfari, M.; Fatemi Ghomi, S. M.T., Group shops scheduling with makespan criterion subject to random release dates and processing times, Comput. Oper. Res., 37, 152-162 (2010) · Zbl 1171.90389 |
| [12] | Ahmadizar, F.; Zarei, A., Minimizing makespan in a group shop with fuzzy release dates and processing times, Int. J. Adv. Manuf. Technol., 66, 2063-2074 (2013) |
| [13] | Rossi, A.; Dini, G., Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method, Rob. Comput. Integr. Manuf., 23, 503-516 (2007) |
| [14] | Gröflin, H.; Klinkert, A., A new neighborhood and tabu search for the blocking job shop, Discrete Appl. Math., 157, 3643-3655 (2009) · Zbl 1185.90076 |
| [15] | Gröflin, H.; Pham, D. N.; Bürgy, R., The flexible blocking job shop with transfer and set-up times, J. Comb. Optim., 22, 121-144 (2011) · Zbl 1226.90036 |
| [16] | Naderi, B.; Zandieh, M.; Balagh, A. K.G.; Roshanaei, V., An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness, Expert Syst. Appl., 36, 9625-9633 (2009) |
| [17] | Artigues, C.; Lopez, P.; Ayache, P. D., Schedule generation schemes for the job-shop problem with sequence-dependent setup times: dominance properties and computational analysis, Ann. Oper. Res., 138, 21-52 (2005) · Zbl 1091.90014 |
| [18] | Artigues, C.; Feillet, D., A branch and bound method for the job-shop problem with sequence-dependent setup times, Ann. Oper. Res., 159, 135-159 (2008) · Zbl 1152.90424 |
| [19] | Brucker, P.; Thiele, O., A branch and bound method for the general-shop problem with sequence-dependent setup times, OR Spektrum, 18, 145-161 (1996) · Zbl 0852.90087 |
| [20] | Hurink, J.; Knust, S., Tabu search algorithms for job-shop problems with a single transport robot, Eur. J. Oper. Res., 162, 99-111 (2005) · Zbl 1132.90324 |
| [21] | Giovanni, L. D.; Pezzella, F., An improved genetic algorithm for the distributed and flexible job-shop scheduling problem, Eur. J. Oper. Res., 200, 395-408 (2010) · Zbl 1177.90195 |
| [22] | Behnamian, J.; Fatemi Ghomi, S. M.T., Hybrid flowshop scheduling with machine and resource-dependent processing times, Appl. Math. Model., 35, 1107-1123 (2011) · Zbl 1211.90077 |
| [23] | Kamrul Hasan, S. M.; Sarker, R.; Essam, D., Genetic algorithm for job-shop scheduling with machine unavailability and breakdowns, Int. J. Prod. Res., 49, 4999-5015 (2011) |
| [24] | Wu, C. C.; Wu, W. H.; Hsu, P. H.; Lai, K., A two-machine flowshop scheduling problem with a truncated sum of processing-times-based learning function, Appl. Math. Model., 36, 5001-5014 (2012) · Zbl 1252.90028 |
| [25] | Behnamian, J.; Fatemi Ghomi, S. M.T.; Jolai, F.; Amirtaheri, O., Minimizing makespan on a three-machine flowshop batch scheduling problem with transportation using genetic algorithm, Appl. Soft Comput., 12, 768-777 (2012) |
| [26] | Chen, J. C.; Wu, C. C.; Chen, C. W.; Chen, K. H., Flexible job shop scheduling with parallel machines using genetic algorithm and grouping genetic algorithm, Expert Syst. Appl., 39, 10016-10021 (2012) |
| [27] | Zhang, Q.; Manier, H.; Manier, M. A., A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times, Comput. Oper. Res., 39, 1713-1723 (2012) · Zbl 1251.90208 |
| [28] | Ahmadizar, F.; Hosseinabadi Farahani, M., A novel hybrid genetic algorithm for the open shop scheduling problem, Int. J. Adv. Manuf. Technol., 62, 775-787 (2012) |
| [29] | Chen, S. H.; Chen, M. C.; Chang, P. C.; Mani, V., Multiple parents crossover operators: a new approach removes the overlapping solutions for sequencing problems, Appl. Math. Model., 37, 2737-2746 (2013) · Zbl 1351.90170 |
| [30] | Eiben, A. E.; Smith, J. E., Introduction to Evolutionary Computing (2003), Springer: Springer Berlin · Zbl 1028.68022 |
| [31] | Sivanandam, S. N.; Deepa, S. N., Introduction to Genetic Algorithms (2008), Springer: Springer New York · Zbl 1129.90001 |
| [33] | Mattfeld, D. C., Evolutionary Search and the Job Shop: Investigations on Genetic Algorithms and Production Scheduling (1995), Springer: Springer Berlin |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
