Target-oriented Robust Satisficing Models for the Single Machine Scheduling Problems with Release Time

This paper investigates single machine scheduling problems with release time and random processing time, where the release time can be either deterministic or random. The objective is to determine a scheduling sequence that performs well in terms of out-of-sample performance. To achieve this, we employ target-oriented robust satisficing models to obtain the scheduling sequence. For the scheduling problem with deterministic release time, we derive an equivalent mixed-integer linear program and an approximate reformulation to address cases involving a large number of jobs. For the scheduling problem with random release time, we initially demonstrate the challenges associated with providing an equivalent reformulation. To overcome this intractability, we propose an approximate reformulation based on the linear decision rule. Numerical experiments are conducted to showcase the superiority of our solutions through comparisons with several benchmarks. Furthermore, the numerical results demonstrate that a relatively higher target should be chosen if the worst-case performance is valued, otherwise, the decision-maker should set a relatively lower target to obtain a better average performance