Multi-resource shop scheduling with resource flexibility. (English) Zbl 0943.90028
Summary: The shop scheduling problem tackled in this paper integrates many features that can be found in practical settings. Every operation may need several resources to be performed, and furthermore, a resource may be selected in a given set of candidates resources. Finally, we also consider that an operation may have more than one predecessor and/or more than one successor on the routing. The problem is then to both assign operations to resources and sequence operations on the resources. in order to minimize the maximum completion time. A disjunctive graph representation of this problem is presented and a connected neighborhood structure is proposed. The latter can be used to derive a local search algorithm such as tabu search. Finally, some numerical experiments are presented and discussed.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Software:
Tabu searchReferences:
| [1] | Brucker, P.; Schlie, R., Job-shop scheduling with multi-purpose machines, Computing, 45, 369-375 (1990) · Zbl 0813.90058 |
| [2] | Brandimarte, P., Routing and scheduling in a flexible job shop by tabu search, Annals of Operations Research, 41, 57-183 (1993) · Zbl 0775.90227 |
| [3] | Hurink, J.; Jurisch, B.; Thole, M., Tabu search fo the job-shop scheduling problem with multi-purpose machines, OR Spektrum, 15, 205-215 (1994) · Zbl 0798.90086 |
| [4] | Paulli, J., A hierarchical approach for the FMS scheduling problem, European Journal of Operational Research, 86, 32-42 (1995) · Zbl 0902.90086 |
| [5] | 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, Annals of Operations Research, 70, 281-306 (1997) · Zbl 0890.90097 |
| [6] | W. Herroelen, E. Demeulemeester, Recent advances in branch-and-bound procedures for resource-constraint project scheduling problems, in: P. Chrétienne et al. (Eds.), Scheduling Theory and its Applications, Wiley, Chichester, 1995, pp. 259-274; W. Herroelen, E. Demeulemeester, Recent advances in branch-and-bound procedures for resource-constraint project scheduling problems, in: P. Chrétienne et al. (Eds.), Scheduling Theory and its Applications, Wiley, Chichester, 1995, pp. 259-274 |
| [7] | van Hee, K. M.; Lenstra, J. K., A comparative study in DSS development, European Journal of Operational Research, 79, 153-157 (1994) |
| [8] | Bianco, L.; Dell’Olmo, P.; Speranza, M. G., Nonpreemptive scheduling of independent tasks with prespecified processor allocations, Naval Research Logistics, 41, 959-971 (1994) · Zbl 0833.90065 |
| [9] | S. Dauzère-Pérès, J. Paulli, Solving the general multiprocessor job-shop scheduling problem, Management Report, Series No. 182, Rotterdam School of Management, Erasmus Universiteit Rotterdam, Pays-Bas, 1994; S. Dauzère-Pérès, J. Paulli, Solving the general multiprocessor job-shop scheduling problem, Management Report, Series No. 182, Rotterdam School of Management, Erasmus Universiteit Rotterdam, Pays-Bas, 1994 |
| [10] | B. Roy, B. Sussman, Les problèmes d’ordonnancement avec contraintes disjonctives, Note DS No. 9 bis, SEMA, Montrouge, 1964; B. Roy, B. Sussman, Les problèmes d’ordonnancement avec contraintes disjonctives, Note DS No. 9 bis, SEMA, Montrouge, 1964 |
| [11] | van Laarhoven, P. M.; Aarts, E. H.L.; Lenstra, J. K., Job shop scheduling by simulated annealing, Operations Research, 40, 113-125 (1992) · Zbl 0751.90039 |
| [12] | Glover, F.; Taillard, E.; de Werra, D., A user’s guide to tabu search, Annals of Operations Research, 41, 3-28 (1993) · Zbl 0772.90063 |
| [13] | Brucker, P.; Hurink, J.; Jurisch, B.; Wöstmann, B., A branch-and-bound algorithm for the open-shop problem, Discrete Applied Mathematics, 76, 43-59 (1997) · Zbl 0882.90066 |
| [14] | C. Guéret, C. Prins, Classical and New Heuristics for the Open-Shop Problem: A Computational Evaluation, Fifth International Workshop on Project Management and Scheduling, Poznan, Poland, 1996, pp. 98-101; C. Guéret, C. Prins, Classical and New Heuristics for the Open-Shop Problem: A Computational Evaluation, Fifth International Workshop on Project Management and Scheduling, Poznan, Poland, 1996, pp. 98-101 |
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.
