The job shop scheduling problem: Conventional and new solution techniques. (English) Zbl 0980.90024
Summary: This survey is devoted to an overview of the solution techniques available for solving the job shop problem. Six double-column pages of references are given.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |
References:
| [1] | Aarts, E. H.L.; Korst, J. H.M., Simulated Annealing and Boltzmann Machines (1989), Wiley: Wiley Chichester · Zbl 0674.90059 |
| [2] | Aarts, E. H.L.; van Laarhoven, P. J.M.; Lenstra, J. K.; Ulder, N. L.J., A computational study of local search shop scheduling, ORSA Journal on Computing, 6, 118-125 (1994) · Zbl 0819.90040 |
| [3] | Adams, J.; Balas, E.; Zawack, D., The shifting bottleneck procedure for job shop scheduling, Management Science, 34, 391-401 (1988) · Zbl 0637.90051 |
| [4] | Aggoun, A.; Beldiceanu, N., Extending CHIP in order to solve complex scheduling and placement problems, Mathematical and Computer Modelling, 17, 57-73 (1993) |
| [5] | Akers, S. B., A graphical approach to production scheduling problems, Operations Research, 4, 244-245 (1956) |
| [6] | Anderson, E. J.; Glass, C. A.; Potts, C. N., Local search in combinatorial optimization: Applications in machine scheduling, (Research Report No. OR56 (1995), University of Southampton) |
| [7] | Applegate, D.; Cook, W., A computational study of the job-shop scheduling problem, ORSA Journal on Computing, 3, 149-156 (1991) · Zbl 0755.90039 |
| [8] | Ashour, S., Sequencing Theory (1972), Springer: Springer Berlin · Zbl 0241.90029 |
| [9] | Ashour, S.; Hiremath, S. R., A branch-and-bound approach to the job-shop scheduling problem, International Journal of Production Research, 11, 47-58 (1973) |
| [10] | Ashour, S.; Moore, T. E.; Chiu, K.-Y., An implicit enumeration algorithm for the nonpreemptive shop scheduling problem, AIIE Transactions, 6, 62-72 (1974) |
| [11] | Baker, K. R., Introduction to Sequencing and Scheduling (1974), Wiley: Wiley New York |
| [12] | Baker, K. R., A comparative study of flow shop algorithms, Operations Research, 23, 62-73 (1975) · Zbl 0307.90037 |
| [13] | Baker, K. R.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints, Operations Research, 31, 381-386 (1983) · Zbl 0442.90040 |
| [14] | Bakshi, M. S.; Arora, S. R., The sequencing problem, Management Science, 16, B247-B263 (1969) · Zbl 0191.48502 |
| [15] | Balas, E., Machine sequencing via disjunctive graphs: An implicit enumeration algorithm, Operations Research, 17, 941-957 (1969) · Zbl 0183.49404 |
| [16] | Balas, E., On the facial structure of scheduling polyhedra, Mathematical Programming Study, 24, 179-218 (1985) · Zbl 0582.90053 |
| [17] | Balas, E.; Lenstra, J. K.; Vazacopoulos, A., One machine scheduling with delayed precedence constraints, Management Science, 41, 94-109 (1995) · Zbl 0824.90076 |
| [18] | Balas, E.; Vazacopoulos, A., Guided local search with shifting bottleneck fo job shop scheduling, Management Science Research Report #MSRR-609 (1995) |
| [19] | Baptiste, P.; Le Pape, C., A theoretical and experimental comparison of constraint propagation techniques for disjunctive scheduling, (Proc. 14th Int. Joint Conference on Artificial Intelligence (IJCAI). Proc. 14th Int. Joint Conference on Artificial Intelligence (IJCAI), Montreal, Canada (1995)) |
| [20] | Baptise, P.; Le Pape, C.; Nuijten, W., Constrained-based optimization and approximation for job-shop scheduling, (Proc. AAAI-SIGMAN Workshop on Intelligent Manufacturing Systems, 14th Int. Joint Conference on Artificial Intelligence (IJCAI). Proc. AAAI-SIGMAN Workshop on Intelligent Manufacturing Systems, 14th Int. Joint Conference on Artificial Intelligence (IJCAI), Montreal, Canada (1995)) |
| [21] | Baptiste, P.; Le Pape, C.; Nuijten, W., Incorporating efficient operations research algorithms in constraint-based scheduling, (Proc. 1st Joint Workshop on Artificial Intelligence and Operations Research. Proc. 1st Joint Workshop on Artificial Intelligence and Operations Research, Timberline Lodge, OR (1995)), (to appear) |
| [22] | Barker, J. R.; McMahon, G. B., Scheduling the general job-shop, Management Science, 31, 594-598 (1985) · Zbl 0609.90066 |
| [23] | Barnes, J. W.; Chambers, J. B., Solving the job shop scheduling problem using tabu search, IIE Transactions, 27, 2 (1994) |
| [24] | Barnes, J. W.; Laguna, M.; Glover, F., An overview of tabu search approaches to production scheduling problems, (Proc. Symposium Intelligent Scheduling Systems. Proc. Symposium Intelligent Scheduling Systems, San Francisco (1992)), 30-50 |
| [25] | Bertier, P.; Roy, B., Trois exemples numeriques d’application de la procedure SEP, Note de travail No. 32 de la Direction Scientifique de la SEMA (1965) |
| [26] | Bierwirth, C., A generalized permutation approach to job shop scheduling with genetic algorithms, OR Spektrum, 17, 87-92 (1995) · Zbl 0843.90056 |
| [27] | Blackstone, J. H.; Phillips, D. T.; Hogg, G. L., A state of the art survey of dispatching rules for manufacturing job shop operations, International Journal Production Research, 20, 27-45 (1982) |
| [28] | Błazewicz, J., Selected topics in scheduling theory, Annals of Discrete Mathematics, 31, 1-60 (1987) · Zbl 0611.90060 |
| [29] | Błazewicz, J.; Dror, M.; Weglarz, J., Mathematical programming formulations for machine scheduling: A survey, European Journal of Operational Research, 51, 283-300 (1991) · Zbl 0734.90040 |
| [30] | Błazewicz, J.; Ecker, K.; Schmidt, G.; Weglarz, J., Scheduling in Computer and Manufacturing Systems (1994), Springer: Springer Heidelberg · Zbl 0816.90068 |
| [31] | Bowman, E. H., The scheduling sequencing problem, Operations Research, 7, 621 (1959) · Zbl 1255.90059 |
| [32] | Brah, S.; Hunsucker, J.; Shah, J., Mathematical modeling of scheduling problems, Journal of Information & Optimization Sciences, 12, 113-137 (1991) · Zbl 0729.90052 |
| [33] | Bräsel, H., Lateinische Rechtecke und Maschinenbelegung, (Dissertation B (1990), Technical University of Magdeburg) |
| [34] | Bräsel, H.; Werner, F., The job-shop problem-modelling by latin rectangles exact and heuristic solution, (Working paper Math 8/89 (1989), Technical University of Magdeburg) · Zbl 0704.90049 |
| [35] | Brooks, G. H.; White, C. R., An algorithm for finding optimal or near-optimal solutions to the production scheduling problem, Journal of Industrial Engineering, 16, 34-40 (1965) |
| [36] | Brucker, P., Scheduling (1981), Akademische Verlagsgesellschaft: Akademische Verlagsgesellschaft Wiesbaden · Zbl 0474.68052 |
| [37] | Brucker, P., An efficient algorithm for the job-shop problem with two jobs, Computing, 40, 353-359 (1988) · Zbl 0654.90036 |
| [38] | Brucker, P., A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs, OR Spektrum, 16, 5-7 (1994) · Zbl 0807.90061 |
| [39] | Brucker, P., Scheduling Algorithms (1995), Springer: Springer Berlin · Zbl 0839.90059 |
| [40] | Brucker, P.; Hurink, J.; Werner, F., Improving local search heuristics for some scheduling problems (1994), University of Osnabrück, Working paper |
| [41] | Brucker, P.; Hurink, J.; Werner, F., Improving local search heuristics for some scheduling problems, Part II (1994), University of Osnabrück, Working paper |
| [42] | Brucker, P.; Jurisch, B., A new lower bound for the job-shop scheduling problem, European Journal of Operational Research, 64, 156-167 (1993) · Zbl 0778.90022 |
| [43] | Brucker, P.; Jurisch, B.; Krämer, A., The job-shop problem and immediate selection (1992), University of Osnabrück, Working paper |
| [44] | Brucker, P.; Jurisch, B.; Sievers, B., Job-shop (C codes), European Journal of Operational Research, 57, 132-133 (1992) |
| [45] | Brucker, P.; Jurisch, B.; Sievers, B., A branch and bound algorithm for the job-shop scheduling problem, Discrete Applied Mathematics, 49, 107-127 (1994) · Zbl 0802.90057 |
| [46] | Burns, F.; Rooker, J., Three-stage flow-shops with recessive second stage, Operations Research, 26, 207-208 (1978) · Zbl 0371.90062 |
| [47] | Campbell, H. G.; Dudek, R. A.; Smith, M. L., A heuristic algorithm for the \(n\) job \(m\) machine sequencing problem, Management Science, 16, 630-637 (1970) · Zbl 0194.50504 |
| [48] | Carlier, J., The one machine sequencing problem, European Journal of Operational Research, 11, 42-47 (1982) · Zbl 0482.90045 |
| [49] | Carlier, J., Scheduling jobs with release dates and tails on identical machines to minimize the makespan, European Journal of Operational Research, 29, 298-306 (1987) · Zbl 0622.90049 |
| [50] | Carlier, J.; Pinson, E., An algorithm for solving the job-shop problem, Management Science, 35, 164-176 (1989) · Zbl 0677.90036 |
| [51] | Carlier, J.; Pinson, E., A practical use of Jackson’s preemptive schedule for solving the job shop problem, Annals of Operations Research, 26, 269-287 (1990) · Zbl 0709.90061 |
| [52] | Carlier, J.; Pinson, E., Adjustments of heads and tails for the job-shop problem, European Journal of Operational Research, 78, 146-161 (1994) · Zbl 0812.90063 |
| [53] | Caseau, Y.; Laburthe, F., Disjunctive scheduling with task intervals (1995), Ecole Normale Supérieure: Ecole Normale Supérieure Paris, Working paper |
| [54] | Caseau, Y., Le Pape, C., and Nuijten, W. (1996), Private communication.; Caseau, Y., Le Pape, C., and Nuijten, W. (1996), Private communication. |
| [55] | Charlton, J. M.; Death, C. C., A generalized machine scheduling algorithm, Operations Research Quarterly, 21, 127-134 (1970) · Zbl 0191.48403 |
| [56] | Cho, Y.; Sahni, S., Preemptive scheduling of independent jobs with release and due times on open, flow and job shops, Operations Research, 29, 511-522 (1981) · Zbl 0455.90043 |
| [57] | Chrétienne, P.; Coffman, E. G.; Lenstra, J. K.; Liu, Z., Scheduling Theory and its Applications (1995), Wiley: Wiley Chichester · Zbl 0873.90049 |
| [58] | Chu, C.; Portmann, M. C.; Proth, J. M., A splitting-up approach to simplify job-shop scheduling problems, International Journal of Production Research, 30, 859-870 (1992) · Zbl 0729.90973 |
| [59] | Clark, W., The Gantt Chart: A Working Tool of Management (1922), The Ronald Press: The Ronald Press New York |
| [60] | (Coffman, E. G., Computer and Job-Shop Scheduling Theory (1976), Wiley: Wiley New York) · Zbl 0359.90031 |
| [61] | Conway, R. N.; Maxwell, W. L.; Miller, L. W., Theory of Scheduling (1967), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 1058.90500 |
| [62] | Crama, Y.; Kolen, A.; Pesch, E., Local search in combinatorial optimization, Lecture Notes in Computer Science, 931, 157-174 (1995) |
| [63] | Crowston, W. B.; Glover, F.; Thompson, G. L.; Trawick, J. D., Probabilistic and parametric learning combinations of local job shop scheduling rules, (ONR Research Memorandum No. 117 (1963), GSIA, Carnegie-Mellon University: GSIA, Carnegie-Mellon University Pittsburg, PA) |
| [64] | Dannenbring, D. G., An evaluation of flow shop scheduling heuristics, Management Science, 23, 1174-1182 (1977) · Zbl 0371.90063 |
| [65] | Dauzere-Peres, S.; Lasserre, J.-B., A modified shifting bottleneck procedure for job-shop scheduling, International Journal of Production Research, 31, 923-932 (1993) · Zbl 0773.90036 |
| [66] | Davis, L., Job shop scheduling with genetic algorithms, (Grefenstette, J. J., Proc. International Conf. on Genetic Algorithms and Their Applications (1985), Lawrence Erlbaum Ass), 136-140 · Zbl 0681.68043 |
| [67] | Day, J. E.; Hottenstein, M. P., Review of sequencing research, Naval Research Logistics Quarterly, 17, 11-39 (1970) · Zbl 0202.18501 |
| [68] | Dechter, R.; Pearl, J., Network-based heuristics for constraint satisfaction problems, Artificial Intelligence, 34, 1-38 (1988) · Zbl 0643.68156 |
| [69] | Della Croce, F.; Tadei, R.; Volta, G., A genetic algorithm for the job shop problem, Computers & Operations Research, 22, 15-24 (1995) · Zbl 0816.90081 |
| [70] | Dell’Amico, M., Shop problems with two machines and time lags (1993), Politecnico di Milano, Working paper |
| [71] | Dell’Amico, M.; Trubian, M., Applying tabu-search to the job shop scheduling problem, Annals of Operations Research, 41, 231-252 (1993) · Zbl 0771.90056 |
| [72] | Domschke, W.; Scholl, A.; Voβ, S., Produktionsplanung (1993), Springer: Springer Berlin |
| [73] | Dorndorf, U.; Pesch, E., Combining genetic and local search for solving the job shop scheduling problem, (Maros, I., Symposium on Applied Mathematical Programming and Modeling APMOD93 (1993), Akaprint: Akaprint Budapest), 142-149 |
| [74] | Dorndorf, U.; Pesch, E., Genetic algorithms for job shop scheduling, (Hansmann, K.-W.; etal., Operations Research Proc. 1992 (1993), Springer: Springer Berlin), 243-250 |
| [75] | Dorndorf, U.; Pesch, E., Variable depth search and embedded schedule neighbourhoods for job shop scheduling, (4th International Workshop on Project Management and Scheduling (1994)), 232-235 |
| [76] | Dorndorf, U.; Pesch, E., Fast clustering algorithms, ORSA Journal on Computing, 6, 141-153 (1994) · Zbl 0820.90114 |
| [77] | Dorndorf, U.; Pesch, E., Evolution based learning in a job shop scheduling environment, Computers & Operations Research, 22, 25-40 (1995) · Zbl 0815.90089 |
| [78] | Dudek, R. A.; Panwalkar, S. S.; Smith, M. L., The lessons of flowshop scheduling research, Operations Research, 40, 7-13 (1992) · Zbl 0825.90554 |
| [79] | Ecker, K., Organisation von parallelen Prozessen (1977), BI-Wissenschaftsverlag: BI-Wissenschaftsverlag Mannheim · Zbl 0408.68027 |
| [80] | Elmaghraby, S. E., The machine sequencing problem-Review and extensions, Naval Research Logistics Quarterly, 15, 205-232 (1968) |
| [81] | Elmaghraby, S. E.; Elshafei, A. N., Branch-and-bound revised: A survey of basic concepts and their applications in scheduling, (Marlow, W. H., Modern Trends in Logistics Research (1976), MIT Press: MIT Press Cambridge, MA) |
| [82] | Fisher, M. L., Optimal solution of scheduling problems using Lagrange multipliers: Part I, Operations Research, 21, 1114-1127 (1973) · Zbl 0294.90085 |
| [83] | Fisher, M. L.; Lageweg, B. J.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Surrogate duality relaxation for job shop scheduling, Discrete Applied Mathematics, 5, 65-75 (1983) · Zbl 0498.90045 |
| [84] | Fisher, H.; Thompson, G. L., Probabilistic learning combinations of local job-shop scheduling rules, (Muth, J. F.; Thompson, G. L., Industrial Scheduling (1963), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ) |
| [85] | Florian, M.; Trépant, P.; McMahon, G., An implicit enumeration algorithm for the machine sequencing problem, Management Science, 17, B782-B792 (1971) · Zbl 0224.90047 |
| [86] | Fox, M. S., Constraint-directed search: A case study of job shop scheduling (1987), Pitman: Pitman London · Zbl 0702.68032 |
| [87] | Fox, M. S.; Smith, S. F., ISIS—A knowledge based system for factory scheduling, Expert Systems, 1, 25-49 (1984) |
| [88] | French, S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop (1982), Wiley: Wiley New York · Zbl 0479.90037 |
| [89] | Gantt, H. L., Efficiency and democracy, Transactions of the American Society of Mechanical Engineers, 40, 799-808 (1919) |
| [90] | Garey, M. R.; Johnson, D. S.; Sethi, R., The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1, 117-129 (1976) · Zbl 0396.90041 |
| [91] | Gere, W. S., Heuristics in job-shop scheduling, Management Science, 13, 167-190 (1966) |
| [92] | Giffler, B.; Thompson, G. L., Algorithms for solving production scheduling problems, Operations Research, 8, 487-503 (1960) · Zbl 0248.90022 |
| [93] | Giffler, B.; Thompson, G. L.; van Ness, V., Numerical experience with the linear and Monte Carlo algorithms for solving production scheduling problems, (Muth, J. F.; Thompson, G. L., Industrial Scheduling (1963), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ) |
| [94] | Glass, C. A.; Potts, C. N.; Shade, P., Genetic algorithms and neighbourhood search for scheduling unrelated parallel machines, (Working paper No. OR47 (1992), University of Southampton) · Zbl 0810.90066 |
| [95] | Glover, F., Tabu search — Part I, ORSA Journal on Computing, 1, 190-206 (1989) · Zbl 0753.90054 |
| [96] | Glover, F., Tabu search — Part II, ORSA Journal on Computing, 2, 4-32 (1990) · Zbl 0771.90084 |
| [97] | Glover, F., Tabu search: A tutorial, Interfaces, 20, 74-94 (1990) |
| [98] | Glover, F., Multilevel tabu search and embedded search neighborhoods for the traveling salesman problem (1991), University of Colorado: University of Colorado Boulder, Working paper |
| [99] | Glover, F., Ejection chains, reference structures and alternating path methods for the traveling salesman problem (1992), University of Colorado: University of Colorado Boulder, Working paper |
| [100] | Glover, F.; Pesch, E., TSP ejection chains, Discrete Applied Mathematics (1995), to appear · Zbl 0883.90120 |
| [101] | Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056 |
| [102] | Gonzalez, T.; Sahni, S., Flowshop and jobshop schedules: Complexity and approximation, Operations Research, 20, 36-52 (1978) · Zbl 0371.90061 |
| [103] | Grabowski, J.; Nowicki, E.; Zdrzalka, S. S., A block approach for single machine scheduling with release dates and due dates, European Journal of Operational Research, 26, 278-285 (1986) · Zbl 0603.90073 |
| [104] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, (Lenstra, J. K.; Rinnooy Kan, A. H.G.; van Emde Boas, P., Interfaces between Computer Science and Operations Research (1978), Mathematical Centre Tracts 99: Mathematical Centre Tracts 99 Amsterdam), 169-231 · Zbl 0388.90032 |
| [105] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling theory: A survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044 |
| [106] | Green, G. I.; Appel, L. B., An empirical analysis of job shop dispatch rule selection, Journal of Operations Management, 1, 197-203 (1981) |
| [107] | Greenberg, H. H., A branch and bound solution to the general scheduling problem, Operations Research, 16, 353-361 (1968) · Zbl 0155.28704 |
| [108] | Gupta, J. N.D.; Reddi, S. S., Improved dominance conditions for the three-machine flowshop scheduling problem, Operations Research, 26, 200-203 (1978) · Zbl 0375.90037 |
| [109] | Han, C. C.; Lee, C. H., Comments on Mohr and Henderson path consistency algorithm, Artificial Intelligence, 36, 125-130 (1988) · Zbl 0709.68534 |
| [110] | Haupt, R., A survey of priority-rule based scheduling, OR Spektrum, 11, 3-16 (1989) · Zbl 0658.90047 |
| [111] | Hax, A. C.; Candea, D., Production and Inventory Management (1984), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ |
| [112] | Hefetz, N.; Adiri, I., An efficient optimal algorithm for the two-machines unit-time job-shop schedule length problem, Mathematics of Operations Research, 7, 354-360 (1982) · Zbl 0498.90042 |
| [113] | van Hentenryck, P.; Deville, Y.; Teng, C.-M., A generic arc-consistency algorithm and its specializations, Artificial Intelligence, 57, 291-321 (1992) · Zbl 0763.68059 |
| [114] | Hilliard, M. R.; Liepins, G. E., Machine learning applications to job shop scheduling, (Proceedings Workshop on Production Planning and Scheduling (1988), AAAI-SIGMAN: AAAI-SIGMAN St. Paul, MN) · Zbl 0796.68167 |
| [115] | Ho, J. C.; Chang, Y-L., A new heuristic for the \(n\)-job, \(M\)-machine flow-shop problem, European Journal of Operational Research, 52, 194-202 (1991) · Zbl 0725.90045 |
| [116] | Hoitomt, D. J.; Luh, P. B.; Pattipati, K. R., A practical approach to job-shop scheduling problems, IEEE Transactions on Robotics and Automation, 9, 1-13 (1993) |
| [117] | Holland, J. H., Adaptation in Natural and Artificial Systems (1975), The University of Michigan Press: The University of Michigan Press Ann Arbor, MI · Zbl 0317.68006 |
| [118] | Hübscher, R.; Glover, F., Applying tabu search with influential diversification to multiprocessor scheduling (1992), University of Colorado: University of Colorado Boulder, Working paper · Zbl 0814.90048 |
| [119] | Hundal, T. S.; Rajgopal, J., An extension of Palmer’s heuristic for the flow-shop scheduling problem, International Journal of Production Research, 26, 1119-1124 (1988) |
| [120] | Husbands, P.; Mill, F.; Warrington, S., Genetic algorithms, production plan optimisation and scheduling, Lecture Notes in Computer Science, 496, 80-84 (1991) |
| [121] | Ignall, E.; Schrage, L., Application of the branch-and bound technique to some flow-shop scheduling problem, Operations Research, 13, 400-412 (1965) |
| [122] | Jackson, J. R., An extension of Johnson’s results on job lot scheduling, Naval Research Logistics Quarterly, 3, 201-203 (1956) |
| [123] | Johnson, D. S., The NP-completeness column: An ongoing guide, Journal of Algorithms, 4, 189-203 (1983) · Zbl 0509.68035 |
| [124] | Johnson, D. S.; Papadimitriou, C. H.; Yannakakis, M., How easy is local search?, Journal of Computer System Science, 37, 79-100 (1988) · Zbl 0655.68074 |
| [125] | Johnson, L. A.; Montgomery, D. C., Operations Research in Production Planning, Scheduling and Inventory Control (1974), Wiley: Wiley New York |
| [126] | Johnson, S. M., Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61-68 (1954) · Zbl 1349.90359 |
| [127] | Kawaguchi, T.; Kyan, S., Deterministic scheduling in computer systems: A survey, Journal of the Operational Research Society Japan, 31, 190-217 (1988) · Zbl 0644.68048 |
| [128] | Kolen, A.; Pesch, E., Genetic local search in combinatorial optimization, Discrete Applied Mathematics, 48, 273-284 (1994) · Zbl 0794.90047 |
| [129] | Kubiak, W.; Sethi, S.; Srishkandarajah, C., An efficient algorithm for a job shop problem, Mathematics of Industrial Systems (1994), to appear |
| [130] | Kusiak, A.; Chen, M., Expert systems for planning and scheduling manufacturing systems, European Journal of Operational Research, 34, 113-130 (1988) |
| [131] | van Laarhoven, P. J.M.; Aarts, E. H.L., Simulated Annealing: Theory and Applications (1987), Reidel: Reidel Dordrecht, Netherlands · Zbl 0643.65028 |
| [132] | van Laarhoven, P. J.M.; Aarts, E. H.L.; Lenstra, J. K., Job shop scheduling by simulated annealing, Operations Research, 40, 113-125 (1992) · Zbl 0751.90039 |
| [133] | Lageweg, B.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Computer aided complexity classification of combinatorial problems, Communications of the ACM, 25, 817-822 (1982) · Zbl 0491.68070 |
| [134] | Lageweg, B.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Job-shop scheduling by implicit enumeration, Management Science, 24, 441-450 (1977) · Zbl 0373.90034 |
| [135] | Lageweg, B.; Lenstra, J. K.; Rinnooy Kan, A. H.G., A general bounding scheme for the permutation flow-shop problem, Operations Research, 26, 53-67 (1978) · Zbl 0371.90059 |
| [136] | Larson, R. E.; Dessouky, M. I.; Devor, R. E., A forward-backward procedure for the single machine problem to minimize maximum lateness, IIE Transactions, 17, 252-260 (1985) |
| [137] | Lawler, E. L., Recent results in the theory of machine scheduling, (Bachem, A.; Grötschel, M.; Korte, B., Mathematical Programming: The State of the Art (1982), Springer: Springer Berlin) · Zbl 0547.90042 |
| [138] | Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Recent developments in deterministic sequencing and scheduling: A survey, (Dempster, M. A.H.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Deterministic and Stochastic Scheduling, Proc. of the NATO Advanced Study and Research Institute on Theoretical Approaches to Scheduling Problems (1982), Reidel: Reidel Dordrecht), 35-73 · Zbl 0482.68035 |
| [139] | Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., Sequencing and scheduling: algorithms and complexity, (Graves, S. C.; Rinnooy Kan, A. H.G.; Zipkin, P. H., Handbooks in Operations Research and Management Science, Vol. 4: Logistics of Production and Inventory (1993), Elsevier: Elsevier Amsterdam) · Zbl 0482.68035 |
| [140] | Lenstra, J. K., Sequencing by Enumerative Methods, (Mathematical Center Tract 69 (1977), Mathematisch Centrum: Mathematisch Centrum Amsterdam) · Zbl 0407.90025 |
| [141] | Lenstra, J. K.; Rinnooy Kan, A. H.G., Computational complexity of discrete optimization problems, Annals of Discrete Mathematics, 4, 121-140 (1979) · Zbl 0411.68042 |
| [142] | Lenstra, J. K.; Rinnooy Kan, R. H.G.; Brucker, P., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 4, 121-140 (1977) · Zbl 0353.68067 |
| [143] | Lourenço, H. R., A computational study of the job-shop and flow shop scheduling problem, (Dissertation (1993), Cornell University: Cornell University Ithaca) |
| [144] | Lourenço, H. R., Job-shop scheduling: Computational study of local search and large-step optimization methods, European Journal of Operational Research, 83, 347-364 (1995) · Zbl 0904.90089 |
| [145] | Mackworth, A. K., Consistency in networks of relations, Artificial Intelligence, 8, 99-118 (1977) · Zbl 0341.68061 |
| [146] | Manne, A. S., On the job shop scheduling problem, Operations Research, 8, 219-223 (1960) |
| [147] | Martin, P.; Shmoys, D., A new approach to computing optimal schedules for the job shop scheduling problem, (Extended Abstract (1995), Cornell University: Cornell University Ithaca) · Zbl 1414.90162 |
| [148] | Mattfeld, D. C., Evolutionary search and the job shop, (Dissertation (1995), University of Bremen) · Zbl 0852.68118 |
| [149] | Matsuo, H.; Suh, C. J.; Sullivan, R. S., A controlled search simulated annealing method for the general jobshop scheduling problem, (Working paper 03-04-88 (1988), University of Texas at Austin) |
| [150] | McMahon, G. B., Optimal production schedules for flow shops, Canadian Operations Research Society Journal, 7, 141-151 (1969) · Zbl 0174.51601 |
| [151] | McMahon, G. B.; Florian, M., On scheduling with ready times and due dates to minimize maximum lateness, Operations Research, 23, 475-482 (1975) · Zbl 0301.90024 |
| [152] | Mellor, P., A review of job shop scheduling, Operations Research Quarterly, 17, 161-171 (1966) |
| [153] | Meseguer, P., Constraint satisfaction problems: An overview, AICOM, 2, 3-17 (1989) |
| [154] | Metropolis, N.; Rosenbluth, A.; Rosenbluth, M.; Teller, A.; Teller, E., Equation of state calculations by fast computing machines, Journal Chemical Physics, 21, 1087-1092 (1953) · Zbl 1431.65006 |
| [155] | Meyer, W., Geometrische Methoden zur Lösung von Job-Shop Problemen und deren Verallgemeinerungen, (Dissertation (1992), University of Osnabrück) · Zbl 0860.90073 |
| [156] | Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs (1992), Springer: Springer Berlin · Zbl 0763.68054 |
| [157] | Minton, S.; Johnston, M. D.; Philips, A. B.; Laird, P., Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems, Artificial Intelligence, 58, 161-205 (1992) · Zbl 0782.90054 |
| [158] | Mohr, R.; Henderson, T. C., Arc and path consistency revisited, Artificial Intelligence, 28, 225-233 (1986) |
| [159] | Monma, C. L.; Rinnooy Kan, A. H.G., A concise survey of efficiently solvable special cases of the permutation flow shop problem, RAIRO, 17, 105-119 (1983) · Zbl 0523.90054 |
| [160] | Montanari, U., Networks of constraints: Fundamental properties and applications to picture processing, Informations Sciences, 7, 95-132 (1974) · Zbl 0284.68074 |
| [161] | Moore, J. M.; Wilson, R. C., A review of simulation research in job shop scheduling, Production and Inventory Management, 8, 1-10 (1967) |
| [162] | (Muth, J. F.; Thompson, G. L., Industrial Scheduling (1963), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ) |
| [163] | Nakano, R.; Yamada, T., Conventional genetic algorithm for job shop problems, (Belew, R. K.; Booker, L. B., Proc. 4th. International Conf. on Genetic Algorithms (1991), Morgan Kaufmann), 474-479 |
| [164] | Nawaz, M.; Enscore, E. E.; Ham, I., A heuristic algorithm for the \(m\)-machine, \(n\)-job flow-shop sequencing problem, Omega, 11, 91-95 (1983) |
| [165] | Nowicki, E.; Smutnicki, C., A fast taboo search algorithm for the job shop problem, Management Science (1993), to appear · Zbl 0880.90079 |
| [166] | Nowicki, E.; Smutnicki, C., A fast tabu search algorithm for the flow shop problem (1994), Technical University Wroclaw, Working paper · Zbl 0814.90050 |
| [167] | Nowicki, E.; Zdrzalka, S., A note on minimizing maximum lateness in a one-machine sequencing problem with release dates, European Journal of Operational Research, 23, 266-267 (1986) · Zbl 0577.90039 |
| [168] | Nuijten, W. P.M., Time and Resource Constrained Scheduling, (Dissertation (1994), Ponsen & Looijen: Ponsen & Looijen Wageningen, The Netherlands) · Zbl 0916.90152 |
| [169] | Nuijten, W. P.M.; Aarts, E. H.L., A computational study of constraint satisfaction for multiple capacitated job shop scheduling, European Journal of Operational Research, 90, 269-284 (1996) · Zbl 0916.90152 |
| [170] | O’Grady, P. J.; Harrison, C., A general search sequencing rule for job shop sequencing, International Journal of Production Research, 23, 951-973 (1985) · Zbl 0569.90046 |
| [171] | Osman, I. H.; Potts, C. N., Simulated annealing for permutation flow shop scheduling, Omega, 17, 551-557 (1989) |
| [172] | Ow, P. S.; Smith, S. F., Viewing scheduling as an opportunistic problem-solving process, Annals of Operations Research, 12, 85-108 (1988) |
| [173] | Palmer, D. S., Sequencing jobs through a multi-stage process in the minimum total time—A quick method of obtaining a near optimum, Operational Research Quarterly, 16, 101-107 (1965) |
| [174] | Panwalkar, S. S.; Iskander, W., A survey of scheduling rules, Operations Research, 25, 45-61 (1977) · Zbl 0369.90054 |
| [175] | Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060 |
| [176] | Perregaard, M.; Clausen, J., Parallel branch-and-bound methods for the job-shop scheduling problem (1995), University of Copenhagen, Working paper |
| [177] | Pesch, E., Machine learning by schedule decomposition (1993), University of Limburg: University of Limburg Maastricht, Working paper |
| [178] | Pesch, E., Learning in Automated Manufacturing (1994), Physica: Physica Heidelberg |
| [179] | Pesch, E.; Tetzlaff, U., Constraint propagation based scheduling of job shops, INFORMS Journal on Computing (1995), to appear |
| [180] | Pinedo, M., Scheduling Theory, Algorithms and Systems (1995), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 1145.90393 |
| [181] | Pinson, E., Le problème de job-shop, (Dissertation (1988), University Paris VI: University Paris VI Paris) · Zbl 0677.90036 |
| [182] | Pinson, E., The job shop scheduling problem: A concise survey and some recent developments (1992), University Catholique de l’Ouest: University Catholique de l’Ouest Angers, France, Working paper |
| [183] | Pirlot, M., General local search heuristics in combinatorial optimization: A tutorial, JORBEL, 32, 7-68 (1992) · Zbl 0768.90062 |
| [184] | Porter, D. B., The Gantt chart as applied to production scheduling and control, Naval Research Logistics Quarterly, 15, 311-317 (1968) |
| [185] | Potts, C. N., An adaptive branching rule for the permutation flow-shop problem, European Journal of Operational Research, 5, 19-25 (1980) · Zbl 0436.90063 |
| [186] | Potts, C. N., Analysis of a heuristic for one machine sequencing with release dates and delivery times, Operations Research, 28, 1436-1441 (1980) · Zbl 0447.90041 |
| [187] | Potts, C. N.; Shmiys, D. B.; Williamson, D. P., Permutation vs. non-permutation flow shop schedules, Operations Research Letters, 10, 281-284 (1991) · Zbl 0742.90045 |
| [188] | Proust, C., De l’influence des idées de S.M. Johnson dans la résolution des problèmes dÓdonnancement de type Flowshop (1992), University F. Rabelais: University F. Rabelais Tours, France, Working paper |
| [189] | Rinnooy Kan, A. H.G., Machine Scheduling Problems: Classification, Complexity and Computations (1976), Nijhoff: Nijhoff The Hague · Zbl 0366.90092 |
| [190] | Röck, H., The three-machine no-wait flow shop problem is NP-complete, Journal of the ACM, 51, 336-345 (1984) · Zbl 0632.68038 |
| [191] | Rodammer, F. A.; White, K. P., A recent review of production scheduling, IEEE Transactions on Systems, Man, and Cybernetics, 18, 841-852 (1988) |
| [192] | Roy, B.; Sussmann, B., Les problèmes d’ordonnancement avec contraintes disjonctives, SEMA, Note D.S. No. 9 (1964), Paris |
| [193] | Sadeh, N., Look-ahead techniques for micro-opportunistic job shop scheduling, (Dissertation (1991), Carnegie Mellon University: Carnegie Mellon University Pittsburgh, PA) |
| [194] | Salvador, M. S., Scheduling and sequencing, (Moder, J. J.; Elmaghraby, S. E., Handbook of Operations Research: Models and Applications (1978), Van Nostrand Reinhold: Van Nostrand Reinhold New York) · Zbl 0438.90004 |
| [195] | Sauer, J., Scheduling and meta-scheduling, (Beierle, C.; Plümer, L., Logic Programming: Formal Methods and Practical Applications (1995), Elsevier: Elsevier Amsterdam) · Zbl 0939.68545 |
| [196] | Smith, S. F.; Fox, M. S.; Ow, P. S., Constructing and maintaining detailed production plans: Investigations into the development of knowledge-based factory scheduling systems, AI Magazine, 46-61 (1986) |
| [197] | Sotskov, Y. N., The complexity of scheduling problems with two and three jobs, European Journal of Operational Research, 53, 326-336 (1991) · Zbl 0742.90046 |
| [198] | Sotskov, Y. N.; Shaklevich, N. V., NP-hardness of shop scheduling problems with three jobs, Discrete Applied Mathematics, 59, 237-266 (1995) · Zbl 0837.90072 |
| [199] | Stafford, E. F., On the development of a mixed-integer linear programming model for the flowshop sequencing problem, Journal of the Operational Research Society, 39, 1163-1174 (1988) · Zbl 0663.90046 |
| [200] | Starkweather, T.; Whitley, D.; Mathias, K.; McDaniel, S., Sequence scheduling with genetic algorithms, (Fandel, G.; Gulledge, T.; Jones, J., New Directions for Operations Research in Manufacturing (1992), Springer: Springer Berlin), 129-148 |
| [201] | Storer, R. H.; Wu, S. D.; Park, I., Genetic algorithms in problem space for sequencing problems, (Fandel, G.; Gulledge, T.; Jones, A., New Directions for Operations Research in Manufacturing, Proc. of the 2nd Joint US/German Conf.. New Directions for Operations Research in Manufacturing, Proc. of the 2nd Joint US/German Conf., Hagen (1992)) |
| [202] | Storer, R. H.; Wu, S. D.; Vaccari, R., Local search in problem and heuristic space for job shop scheduling genetic algorithms, (Fandel, G.; Gulledge, T.; Jones, A., New Directions for Operations Research in Manufacturing, Proc. of a Joint US/German Conf.. New Directions for Operations Research in Manufacturing, Proc. of a Joint US/German Conf., Gaithersburg, Maryland (1991)) · Zbl 0843.90059 |
| [203] | Storer, R. H.; Wu, S. D.; Vaccari, R., New search spaces for sequencing problems with application to job shop scheduling, Management Science, 38, 1495-1509 (1992) · Zbl 0759.90048 |
| [204] | Storer, R. H.; Wu, S. D.; Vaccari, R., Problem and heuristic space search strategies for job shop scheduling (1992), Lehigh University: Lehigh University Bethlehem, PA, Working paper |
| [205] | Sun, D.; Batta, R.; Lin, L., Effective job shop scheduling through active chain manipulation, Computers & Operations Research, 22, 159-172 (1995) · Zbl 0812.90072 |
| [206] | Szwarc, W., Elimination methods in the \(m\) × \(n\) sequencing problem, Naval Research Logistics Quarterly, 18, 295-305 (1971) · Zbl 0237.90044 |
| [207] | Szwarc, W., Optimal elemination methods in the \(m\) × \(n\) sequencing problem, Operations Research, 21, 1250-1259 (1973) · Zbl 0274.90020 |
| [208] | Szwarc, W., Dominance conditions for the three-machine flow shop problem, Operations Research, 26, 203-206 (1978) · Zbl 0379.90052 |
| [209] | Taillard, E., Parallel taboo search technique for the job shop scheduling problem, ORSA Journal on Computing, 6, 108-117 (1994) · Zbl 0807.90066 |
| [210] | Taillard, E., Some efficient heuristic methods for the flow shop sequencing problem, European Journal of Operational Research, 47, 65-74 (1990) · Zbl 0702.90043 |
| [211] | Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 278-285 (1993) · Zbl 0769.90052 |
| [212] | Tanaev, V. S.; Gordon, V. S.; Shafransky, Y. M., Scheduling Theory: Single-Stage Systems (1994), Kluwer Academic Publ: Kluwer Academic Publ Dordrecht · Zbl 0827.90079 |
| [213] | Tanaev, V. S.; Sotskov, Y. N.; Strusevich, V. A., Scheduling Theory: Multi-Stage Systems (1994), Kluwer Academic Publ: Kluwer Academic Publ Dordrecht · Zbl 0925.90224 |
| [214] | Thompson, G. L.; Zawack, D. J., A problem expanding parametric programming method for solving the job shop scheduling problem, Annals of Operations Research, 4, 327-342 (1985/1986) |
| [215] | Turner, S.; Booth, D., Comparison of heuristics for flow shop sequencing, Omega, 15, 75-78 (1987) |
| [216] | Ulder, N. L.J.; Aarts, E. H.L.; Bandelt, H.-J.; van Laarhoven, P. J.M.; Pesch, E., Genetic local search algorithms for the traveling salesman problem, Lecture Notes in Computer Science, 496, 109-116 (1991) |
| [217] | Vaessens, R. J.M., Generalized job shop scheduling: Complexity and local search, (Dissertation (1995), University of Technology: University of Technology Eindhoven) · Zbl 0880.90082 |
| [218] | Vaessens, R. J.M.; Aarts, E. H.L.; Lenstra, J. K., Job shop scheduling by local search (1995), University of Technology: University of Technology Eindhoven, Working paper |
| [219] | van de Velde, S., Machine scheduling and Lagrangian relaxation, (Dissertation (1991), CWI: CWI Amsterdam) · Zbl 0728.90046 |
| [220] | Wagner, H. M., An integer linear programming model for machine scheduling, Naval Research Logistics Quarterly, 6, 131 (1959) |
| [221] | White, K. P.; Rogers, R. V., Job-shop scheduling: Limits of the binary disjunctive formulation, International Journal of Production Research, 28, 2187-2200 (1990) |
| [222] | Widmer, M.; Hertz, A., A new heuristic method for the flow shop sequencing problem, European Journal of Operational Research, 41, 186-193 (1989) · Zbl 0671.90040 |
| [223] | Yamada, T.; Nakano, R., A genetic algorithm applicable to large-scale job-shop problems, (Männer, R.; Manderick, B., Parallel Problem Solving from Nature, 2 (1992), Elsevier: Elsevier Amsterdam), 281-290 |
| [224] | Yannakakis, M., The analysis of local search problems and their heuristics, Lecture Notes in Computer Science, 415, 298-311 (1990) · Zbl 0778.90058 |
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.
