Single‐machine scheduling with no idle time and release dates to minimize a regular criterion

We address the one‐machine scheduling problem with release dates, in which the machine is subject to the non‐idling constraint, i.e. no intermediate idle time is permitted between the jobs processed by the machine. The objective is to minimize a regular objective function. We describe a constraint programming approach for solving this type of problem exactly. Some necessary and/or sufficient conditions for obtaining non‐idling semi‐active, active and optimal schedules are described. We propose some propagation rules based on these properties. As an application, we apply the proposed method to the total (weighted) completion time problem, and we provide some experimental results to illustrate its effectiveness.