The multiple resource constrained project scheduling problem: A breadth-first approach |
| |
| Institution: | 1. Department of Management Studies, Indian Institute of Technology Madras, Chennai 600 036, India;2. Operations Management Group, Indian Institute of Management Calcutta, Kolkata 700 104, India;1. The Hamlyn Centre, Institute of Global Health Innovation, Imperial College, London, UK;2. Department of Surgery and Cancer, St Mary''s Hospital, Imperial College, London, UK;3. Department of Paediatric Surgery, Leeds General Infirmary, Leeds, UK;1. Marketing Area, Indian Institute of Management Bangalore, India;2. Production and Operations Management Area, Indian Institute of Management Bangalore, India |
| |
| Abstract: | We describe a simple breadth-first tree search scheme for minimizing the makespan of a project consisting of a partially ordered network of activities under multiple resource constraints. The method compares quite favourably with existing techniques that employ depth-first or best-first search; in particular, it is able to solve optimally on a Pentium PC running SCO UNIX the entire set of 680 benchmark problems (First Lot: 480, Second Lot: 200) generated by Kolisch et al., 1995. The new algorithm has also been checked out experimentally on additional random test problems at graded levels of difficulty that were generated using two parameters: the threshold, which determined the predecessors of an activity, and the total resource availability of each resource type. The breadth-first scheme can be modified quite readily to do best-first search or to minimize measures other than makespan such as mean flow time and maximum tardiness. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
