An approach for solving a class of transportation scheduling problems
| Autor: | Bezalel Gavish, E. Shlifer |
|---|---|
| Rok vydání: | 1979 |
| Předmět: |
Linear bottleneck assignment problem
Mathematical optimization Schedule Information Systems and Management General Computer Science Job shop scheduling Branch and bound Computer science Quadratic assignment problem Dynamic priority scheduling Management Science and Operations Research Travelling salesman problem Industrial and Manufacturing Engineering Fair-share scheduling Multiprocessor scheduling Deadline-monotonic scheduling Scheduling (computing) Nurse scheduling problem Modeling and Simulation Assignment problem Generalized assignment problem Weapon target assignment problem |
| Zdroj: | European Journal of Operational Research. 3:122-134 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/0377-2217(79)90098-5 |
| Popis: | An algorithm is developed for solving a class of transportation scheduling problems. It applies for a variety of problems such as: the Combining Truck Trip problem, the Delivery problem, the School Bus problem, the Assignment of Buses to Schedules, and the Travelling Salesman problem. The objective functions of the above problems differ from each other. Yet, by using the “savings method” proposed by Clarke and Wright, and extended by Gaskell, we are able to define each one of the above problems as a series of assignment problems. The cost matrix entries of each one of the assignment problems are a function of the constraints of the particular routing or scheduling problem. The solution to the assignment problem determines an upper bound of the optimal solution to the original problem. By combining the above procedure with a Branch and Bound procedure, it is possible to obtain the optimal solution in a finite number of steps. In some cases the Branch and Bound process can be eliminated due to the nature of the problem and in those cases the algorithm is efficient. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|