Solving The Single Machine Scheduling Problem with Sequence-dependent Setup Time, Precedence Delays and the Limitation of Access to Machines

Abstract

In the field of operation scheduling, one of the common assumptions is the availability of machines in the planning horizon. In practice, a machine may be temporarily unavailable for various reasons, such as a breakdown or preventive maintenance. Also, another common assumption in the field of operation scheduling is the availability of tasks at the zero moment. In many cases, some tasks are not available from the beginning of the planning horizon. In the present research, the problem of single machine scheduling with sequence-dependent setup time, precedence delays, job release time and the limit of access to machines has been investigated. Precedence Delays constraint mean that certain pairs of tasks require a delay between the completion time of the previous task and the start time of the next task. Real examples of these cases can be seen in the textile, printing, chemical, pharmaceutical and metallurgical industries. The goal is to find a practical schedule of tasks that meets the constraints of the problem and ultimately minimizes the objective function of the problem, which is the maximum completion time. For the discussed problem, a mixed integer linear programming model is presented to obtain the optimal solution for small and medium size problems in a reasonable time. In order to evaluate the mathematical model, several problems with different specifications and sizes were randomly created and then solved in the GAMS software. Finally, in order to verify the validity of the presented model, sensitivity analysis has been performed on some important parameters of the model.