טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentChen Kaminer
SubjectThe Due-Date Assignment Problem in Scheduling: A Robust
Optimization Approach
DepartmentDepartment of Industrial Engineering and Management
Supervisors Dr. Naseraldin Hussein
Dr. Yedidsion Liron
Full Thesis textFull thesis text - English Version


Abstract

Scheduling is a crucial aspect of operations control, be it in manufacturing or in service.  The need to shrink Time-To-Market, subject to the inherent uncertainties in the input data, and the need to increase service levels necessitate efficient scheduling.  There are various types of scheduling problems that the decision maker faces.  Among others, the Due Date Assignment Problem (DDAP), in which the objective is to minimize the cumulative jobs' earliness, tardiness, and due date assignment costs. Classic DDAP models refer to jobs' processing times as deterministic. However, for practical purposes, jobs' processing times vary due to uncertainties in the input data, e.g., machine break, the newly hired operator, and raw material quality, among others. In most cases it is hard to predict the distribution of the processing time in advance. To cope with the hurdle posed by these uncertainties, Robust Optimization has been emerging as a promising methodology to solicit robust solutions that immunize the system against the various realizations of the uncertain input data. In this research we focused on uncertain DDAPs by utilizing the notions behind the methodology of Robust Optimization.  We consider the uncertain case of the DDAP with single machine, in which the job processing time is uncertain. The scheduler has to determine the common (or different) due date(s) and sequence so as to minimize the total earliness, tardiness, and due date penalties. We focus on two of the most studied DDAP models: The first, where each job has a DIFferent due date, thus denoted by DIF; and the second where all jobs share a COmmoN due date, thus denoted by CON. We extend the DIF model to include buffers for the start time of each job. We distinguish the cases where buffers are helpful and show that for these cases the buffers eliminate the dependency between the jobs and reduce the cumulative impact of the uncertainty on the jobs’ earliness and tardiness. We solve this problem in linear-time. For the CON model we solve the DDAP in a polynomial-time. In both cases we find the jobs’ robust optimal due dates and sequence that create an immune schedule to the process time uncertainty.

Key words: Due Date Assignment Problem; Robust Optimization; Operations management; Complexity; Worst-Case Analysis