Exact and approximate solution methods for batch scheduling problems

点击翻译按钮获取中文摘要

***In production and service industries, the scheduling and sequencing of activities play a crucial role in the efficient allocation of tasks to resources. Batch scheduling is the type of scheduling in which multiple jobs are grouped and processed together. Some examples where batch scheduling is encountered are semiconductor manufacturing, furniture manufacturing, chemical production, metal industry, textile industry, transportation, etc. Vis-à-vis the Canadian economy, two very important sectors where batch scheduling is encountered are steel and aluminum production. In 2017, these industries employed more than a total of 33,000 people and contributed around $9 billion to Canada's gross domestic product. ***Decision making in production planning is a dynamic process and the application of a general (daily, weekly, etc.) policy is unlikely to be determined. Analytical models can be used to take optimal (or close to optimal) batching decisions. Most of the time, these models are helpful to solve only small size problems because of their mathematical complexity. Our aim is to develop efficient solution methods for a generic model that incorporates as many of the more crucial realistic aspects of the batch scheduling problem as we can.***While the batch scheduling literature is rich in heuristic and metaheuristic solution methods, mathematical decomposition methods and exact algorithms are developed for a few problems with simplified hypotheses. With regards to approximation algorithms, most of the existing work has focused on makespan minimization. The proposed research program seeks to develop novel solution techniques by grouping real-life hypotheses such as parallel machines, job release dates, due dates, job families, job dimensions, etc. At first, we will focus on mathematical decomposition methods based on time indexed column generation models (also coupled with row generation depending on the problem type) capable of representing real-life hypotheses. Then we will continue with another setting in which problem data is not fully known in advance. For that setting, we will develop online approximation algorithms to take real-time batching decisions. It is also crucial to test how optimizing the batching step effects the efficiency of the overall system. For that purpose, we will build a generic simulation model for steel production and integrate previously developed batching algorithms as scheduling decisions in that simulation model.***The proposed research targets primarily the Operations Research (OR) community, but it also intends to allow practitioners to take optimum decisions in production planning and scheduling. I also expect the outcome of this research to generate new research ideas for the OR community and help to improve the notion of applying OR techniques in production industries.