| Автор | Werner, F. |
| Дата выпуска | 1993 |
| dc.description | We consider the one-machine scheduling problem with the weighted sum of completion times as objective function. Each job must be completed by a given deadline. The problem is NP-hard. Therefore, various branch and bound algorithms have been developed. We present new criteria for eliminating nodes which are based on the well-known block interchange lemma for estimating the objective function difference when two adjacent blocks of jobs of a sequence are interchanged. Computational results on problems with up to 50 jobs are given. Furthermore, we give a new type of local search algorithm which can be used for improving the upper bound |
| Формат | application.pdf |
| Издатель | Gordon and Breach Science Publishers |
| Копирайт | Copyright Taylor and Francis Group, LLC |
| Тема | One-Machine Scheduling |
| Тема | Branch and Bound Algorithms |
| Название | A branch and bound algorithm for minimizing weighted completion times with deadlines |
| Тип | research-article |
| DOI | 10.1080/02331939308843913 |
| Electronic ISSN | 1029-4945 |
| Print ISSN | 0233-1934 |
| Журнал | Optimization |
| Том | 28 |
| Первая страница | 187 |
| Последняя страница | 199 |
| Аффилиация | Werner, F.; Inst. fur Mathematische Optimierung, Technische Universität “Otto von Guericke” Magdeburg |
| Выпуск | 2 |
| Библиографическая ссылка | Bagchi, U. and Ahmadi, R.H. 1987. An Improved Lower Bound for Minimizing Weighted Completion Times with Deadlines. Operations Res, 35: 311–313. |
| Библиографическая ссылка | Bansal, S.P. 1980. Single Machine Scheduling to Minimize Weighted Sum of Completion Times with Secondary Criterion—a Branch and Bound Approach. European J. Oper. Res, 5: 177–181. |
| Библиографическая ссылка | Boenchendorf, K. 1982. Reihenfolgeprobleme/ Mean-Flow-Time Sequencing, Mathematical Systems in Economics 74, Ahten um. |
| Библиографическая ссылка | Burns, R.N. 1980. Scheduling to Minimize the Weighted Sum of Completion Times with Secondary Criteria. Navel Res. Log. Quart, 23: 177–181. |
| Библиографическая ссылка | Brucker, P., Hurink, J. and Werner, F. 1993. “Improving Neighbourhoods for Local Search Heuristics”. In Osnabrücker Schriften zur Mathematik, Vol. 154, Heft: Reihe P. |
| Библиографическая ссылка | Hariri, A.M.A. and Potts, C.N. 1983. An Algorithm for Single Machine Sequencing with Release Dates to Minimize Total Weighted Completion Time. Discrete Appl. Math, 5: 99–109. |
| Библиографическая ссылка | Miyazaki, S. 1981. One-Machine Scheduling with Dual Criteria. J. Oper. Res. Soc. Japan, 24: 31–50. |
| Библиографическая ссылка | Posner, M.E. 1985. Minimizing Weighted Completion Times with Deadlines. Oper. Res, 33(3): 562–574. |
| Библиографическая ссылка | Potts, C.N. and Van Wassenhove, L.N. 1983. An Algorithm for Single Machine Sequencing with Deadlines to Minimize Total Weighted Completion Time. European J. Oper. Res, 12(3): 379–387. |
| Библиографическая ссылка | Rinnooy Kan, A.H.G. 1976. Machine Scheduling Problems, The Hague: Martinus Nijhoff. |
| Библиографическая ссылка | Shanthikumar, J.G. and Buzacott, J.A. 1982. On the Use of Decomposition Approaches in the Single Machine Scheduling Problem. J. Oper. Res. Soc. Japan, 25: 29–47. |
| Библиографическая ссылка | Smith, W.E. 1956. Various Optimizers for Single-Stage Production. Navel Res. Log. Quart, 3: 59–66. |
