Simultaneous consideration of sequence-dependent and position-dependent setup times in single machine scheduling problems

Abstract

In this work we address a single machine scheduling problems with sequence-dependent setup times, in which the setup time and the processing time may depend on the job position in the processing order. We consider two manufacturing environments. In the first one, jobs are processed automatically, then the job positions affect only on the setup times. In the second environment, the operators modify the machine settings between different types of jobs and operate it to process the jobs, then the job positions affect both setup time and processing time. In this work, we will investigate the validity of the assumption: scheduling problems render high-quality solutions that reckon with job positions just as the those reckoned without job positions. Minimising the maximum completion time and the sum of completion time of the jobs are the objective functions. To tackle this scenario, we introduce four mathematical formulations: one formulation for each combination of objective function and manufacturing environment. The validity of the models is established by the results of extensive computational experiments on the proposed models.