Heuristics for the Cutting Stock with Setup Cost and Blood Collection Problems

The application of Operations Research techniques enables decision makers to come up with better decisions for a wide range of problems in different industries. During last decades, Operations Research solution methods have been attained a huge interest in production planning, supply chain management, health care and many other research areas. In this dissertation, two different problems in the industry and health care settings are studied: (i) the Cutting Stock Problem with Setup Cost, and (ii) the Integrated Collection and Appointment Scheduling Problem. Both problems are analyzed, and solution approaches are developed using Operations Research methodologies. The first problem addresses the Cutting Stock Problem with Setup Cost (CSP-S), which is a more general case of the well-known Cutting Stock Problem (CSP). In CSP-S, different cost factors for the material usage and the number of setups are considered. The objective is to minimize the total production cost including both material and setup costs. A mixed integer linear programming model is developed for CSP-S. To solve the problem efficiently, two local search algorithms, a pool pattern based approach and a column generation based heuristic algorithm are proposed. The effectiveness of the proposed algorithms is demonstrated on the instances from the literature. The second problem is the Integrated Collection and Appointment Scheduling Problem (ICASP). The blood products have limited life time and are required to be collected from donation centers and delivered to a processing center for blood product extraction within a processing time limit. For this problem, a mixed integer programming model is developed to maximize the amount of donated blood that can be delivered for platelet extraction and to determine the preferred schedule of donation appointments accordingly. An Integer Programming Based Algorithm and a Construction Based Heuristic Approach are presented to find good feasible solutions within reasonable time. We also consider the case when the number of donors is uncertain. A Robust Optimization approach is utilized to address different types of data uncertainty and find a robust feasible solution for different scenarios. Also, a Chance Constrained Program is proposed to find routing schedules for the stochastic problem.