The SPLP-model in scheduling and routing (SPLP: simple plant location problem) | |
| Author | Singh, Kashi Naresh |
| Call Number | AIT Diss. no. IE-85-01 |
| Subject(s) | Industries, Location of--Mathematical models Scheduling (Management) |
| Note | A dissertation submitted in partial fulfilment of the requirements for the degree of Doctor of Engineering, School of Engineering and Technology |
| Publisher | Asian Institute of Technology |
| Abstract | The simple plant location problem is a well - studied combinatorial problem which has been extensively used in locational decision- making. In this dissertation, we explore the application of this model in scheduling and routing. Three problems , namely, i) dynamic lot size problem ii) traveling purchaser problem and iii) bus route design problem are selected from this area for study. A single product dynamic lot size problem with and without backlogging is modeled and solved as an SPLP. It is further shown that some of its extensions e . g . , problems with capacity restrictions and those involving joint pricing and production decisions can also be solved by using an SPLP algorithm or an adaptation of it. For the lot size problem, the SPLP algorithm outperforms the traditional dynamic programming algorithms by an order of magnitude or more. The former turns out to be better with viewpoints of storage requirements as well. A branch and bound algorithm which determines the bound by solving a related SPLP is developed for the traveling purchaser problem. Computational experience with this algorithm provides the evidence that problems of upto 20 cities and 100 commodities can be solved in reasonable computation time. This represents a significant improvement over the existing best known results. The traveling purchaser problem has applications in job scheduling, warehousing, routing and network design. Its extensions to stochastic and dynamic cases can also be attempted by the same algorithm. The bus route design problem which involves determining optimal route network for a bus service in a city is modeled as a set covering problem when the demand for the transit is fixed and as an SPLP when the demand is variable. These models are tested on transportation data collected from Kanpur metropolis in India. This approach has the advantage that it considers the actual road network unlike many other approaches which assume a rectangular grid. The major outcome of this work is that we find applications of the SPLP-model to problems which do not necessarily involve locational decision-making and at the same time we come up with alternative approaches provably better than the existing ones for the problems studied in this dissertation. |
| Year | 1985 |
| Type | Dissertation |
| School | School of Engineering and Technology (SET) |
| Department | Other Field of Studies (No Department) |
| Academic Program/FoS | Industrial Engineering (IE) |
| Chairperson(s) | Oudheusden, Dirk L. van |
| Examination Committee(s) | Tabucanon, Mario T. ;Vilas Wuwongse ;Vrat, Prem ;Kaufman, L. |
| Scholarship Donor(s) | The Government of Japan |
| Degree | Thesis (Ph.D.) - Asian Institute of Technology, 1985 |