Mathematical models for job-shop scheduling problems with routing and process plan flexibility. (English) Zbl 1193.90109
Summary: As a result of rapid developments in production technologies in recent years, flexible job-shop scheduling problems have become increasingly significant. This paper deals with two NP-hard optimization problems: flexible job-shop scheduling problems (FJSPs) that encompass routing and sequencing sub-problems, and the FJSPs with process plan flexibility (FJSP-PPFs) that additionally include the process plan selection sub-problem. The study is carried out in two steps. In the first step, a mixed-integer linear programming model (MILP-1) is developed for FJSPs and compared to an alternative model in the literature (Model F) in terms of computational efficiency. In the second step, one other mixed-integer linear programming model, a modification of MILP-1, for the FJSP-PPFs is presented along with its computational results on hypothetically generated test problems.
Keywords:
job-shop scheduling; routing flexibility; process plan flexibility; mixed-integer programmingReferences:
| [1] | Graves, S. C., A review of production scheduling, Oper. Res., 29, 4, 646-675 (1981) · Zbl 0464.90034 |
| [2] | Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., Sequencing and scheduling: algorithms and complexity, (Graves, S. C.; etal., Handbooks in OR and MS, vol. 4 (1993), Elsevier Science Publishers B.V.), 445-522 |
| [3] | Lee, C.-Y.; Lei, L.; Pinedo, M., Current trends in deterministic scheduling, Ann. Oper. Res., 70, 1-41 (1997) · Zbl 0890.90102 |
| [4] | Jain, A. S.; Meeran, S., Deterministic job-shop scheduling: past, present and future, Eur. J. Oper. Res., 113, 390-434 (1999) · Zbl 0938.90028 |
| [5] | Beck, J. C.; Fox, M. S., Constraint-directed techniques for scheduling alternative activities, Artif. Intell., 121, 211-250 (2000) · Zbl 0948.68009 |
| [6] | Kacem, I.; Hammadi, S.; Borne, P., Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic, Math. Comput. Simulat., 60, 245-276 (2002) · Zbl 1006.90044 |
| [7] | Chan, F. T.S.; Wong, T. C.; Chan, L. Y., Flexible job-shop scheduling problem under resource constraints, Int. J. Prod. Res., 44, 11, 2071-2089 (2006) · Zbl 1095.90035 |
| [8] | Ho, N. B.; Tay, J. C.; Lai, E. M.-K., An effective architecture for learning and evolving flexible job-shop schedules, Eur. J. Oper. Res., 179, 316-333 (2007) · Zbl 1180.90121 |
| [9] | Brandimarte, P., Routing and scheduling in a flexible job shop by tabu search, Ann. Oper. Res., 41, 3, 157-183 (1993) · Zbl 0775.90227 |
| [10] | Dauzère-Pérès, S.; Paulli, J., An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search, Ann. Oper. Res., 70, 281-306 (1997) · Zbl 0890.90097 |
| [11] | Dauzère-Pérès, S.; Roux, W.; Lasserre, J. B., Multi-resource shop scheduling with resource flexibility, Eur. J. Oper. Res., 107, 289-305 (1998) · Zbl 0943.90028 |
| [12] | Scrich, C. R.; Armentano, V. A.; Laguna, M., Tardiness minimization in a flexible job shop: a tabu search approach, J. Intell. Manuf., 15, 103-115 (2004) |
| [13] | Saidi-Mehrabad, M.; Fattahi, P., Flexible job shop scheduling with tabu search algorithms, Int. J. Adv. Manuf. Technol., 32, 563-570 (2007) |
| [14] | Low, C.; Wu, T.-H., Mathematical modelling and heuristic approaches to operation scheduling problems in an FMS environment, Int. J. Prod. Res., 39, 4, 689-708 (2001) · Zbl 1060.90647 |
| [15] | Loukil, T.; Teghem, J.; Fortemps, P., A multi-objective production scheduling case study solved by simulated annealing, Eur. J. Oper. Res., 179, 709-722 (2007) · Zbl 1163.90498 |
| [16] | Rossi, A.; Dini, G., Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method, Robot. Comput. Integr. Manuf., 23, 503-516 (2007) |
| [17] | Xia, W.; Wu, Z., An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems, Comput. Ind. Eng., 48, 409-425 (2005) |
| [18] | Gao, J.; Gen, M.; Sun, L., Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm, J. Intell. Manuf., 17, 493-507 (2006) |
| [19] | Low, C.; Yip, Y.; Wu, T.-H., Modelling and heuristics of FMS scheduling with multiple objectives, Comput. Oper. Res., 33, 674-694 (2006) · Zbl 1077.90026 |
| [20] | Fattahi, P.; Saidi-Mehrabad, M.; Jolai, F., Mathematical modeling and heuristic approaches to flexible job shop scheduling problems, J. Intell. Manuf., 18, 331-342 (2007) |
| [21] | Gao, J.; Sun, L.; Gen, M., A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems, Comput. Oper. Res., 35, 2892-2907 (2008) · Zbl 1144.90379 |
| [22] | Vilcot, G.; Billaut, J.-C., A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem, Eur. J. Oper. Res., 190, 398-411 (2008) · Zbl 1146.90427 |
| [23] | Lee, Y. H.; Jeong, C. S.; Moon, C., Advanced planning and scheduling with outsourcing in manufacturing supply chain, Comput. Ind. Eng., 43, 351-374 (2002) |
| [24] | Kim, Y. K.; Park, K.; Ko, J., A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling, Comput. Oper. Res., 30, 1151-1171 (2003) · Zbl 1049.90026 |
| [26] | Baykasoğlu, A.; Özbakır, L.; Sönmez, A.İ., Using multiple objective tabu search and grammars to model and solve multi-objective flexible job-shop scheduling problems, J. Intell. Manuf., 15, 6, 777-785 (2004) |
| [27] | Baykasoğlu, A., Linguistic-based meta-heuristic optimization model for flexible job-shop scheduling, Int. J. Prod. Res., 40, 17, 4523-4543 (2002) · Zbl 1064.90541 |
| [28] | Shapiro, J. F., Mathematical programming models and methods for production planning and scheduling, (Graves, S. C.; etal., Handbooks in OR and MS, vol. 4 (1993), Elsevier Science Publishers B.V.), 371-443 |
| [29] | Pan, C.-H., A study of integer programming formulations for scheduling problems, Int. J. Syst. Sci., 28, 1, 33-41 (1997) · Zbl 0873.90054 |
| [30] | Kim, K.-H.; Egbelu, P. J., Scheduling in a production environment with multiple process plans per job, Int. J. Prod. Res., 37, 12, 2725-2753 (1999) · Zbl 0949.90574 |
| [31] | Brandimarte, P., Exploiting process plan flexibility in production scheduling: a multi-objective approach, Eur. J. Oper. Res., 114, 59-71 (1999) · Zbl 0946.90018 |
| [32] | Thomalla, C. S., Job shop scheduling with alternative process plans, Int. J. Prod. Econ., 74, 125-134 (2001) |
| [33] | Choi, I.-C.; Choi, D.-S., A local search algorithm for jobshop scheduling problems with alternative operations and sequence-dependent setups, Comput. Ind. Eng., 42, 43-58 (2002) |
| [34] | Gomes, M. C.; Barbosa-Povoa, A. P.; Novais, A. Q., Optimal scheduling for flexible job shop operation, Int. J. Prod. Res., 43, 11, 2323-2353 (2005) · Zbl 1068.90057 |
| [35] | Manne, A. S., On the job-shop scheduling problem, Oper. Res., 8, 219-223 (1960) |
| [36] | Wagner, H. M., An integer linear-programming model for machine scheduling, Nav. Res. Logist. Quart., 6, 131-140 (1959) |
| [37] | Bowman, E. H., The scheduling-sequence problem, Oper. Res., 7, 621-624 (1959) · Zbl 1255.90059 |
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.
