Project Details

[Return to Previous Page]

A heuristic for set partitioning problems with applications in service industries.

Company: PSU Industrial and Manufacturing Engineering (IME) 3

Major(s):
Primary: IE
Secondary: CMPSC

Non-Disclosure Agreement: NO

Intellectual Property: NO

Students should be familiar with some programming language like Java or Python. Programming expertise is not required, but there will be no time to learn programming from scratch. In addition, students who have taken (or are concurrently taking) IE 460 and/or IE 405 will have an advantage. Large airlines and hospitals will have 100s of beds or flights and 100s of staff. These organizations need to schedule their staff to flights or to hospital shifts. Students will illustrate the scheduling problem using small textbook examples. Mathematical models will be prepared and then solved with Excel. Students will use the simple example to argue that: 1) for large problems, it is difficult to prepare a mathematical model manually 2) approximate solutions that are based on experience can be sub-optimal 3) software programs may also take a long time to generate a solution, depending on the problem size. Therefore, we need a way to prepare and solve models using a computer. Plus, faster ways of solving these models can be very useful. Students will be expected to look for problems in various service (or manufacturing) industries that can be modelled as set partitioning or covering problems. In addition, students must get some publicly available data sets that can be used to model these problems. For example, assigning hospital nursing staff to shifts is a set partitioning problem. Students must also get some public data set from some hospital about how many nurses they have, how many shifts they have, and so on. The transportation industry also has some problems which will be suitable for this project. Data sets from other industries can also be used with the project advisor's consent. Students will perform a literature review of various techniques available for solving set partitioning and covering problems, or related. They will also identify various industries and the operations during which such problems arise. Students will illustrate the intuitive justification behind the proposed heuristics for solving such problems. They will develop a computer program with guidance from the project advisor. Each student will develop a different portion of the computer program. There are some public problem sets available. These are small problems and not from any particular industry. These will be used for testing. If the computer program seems to be working well, students will apply it on industry problems. The computer program may need to be refined based on what is working well and what is not.