Recently, the setup times or costs have become an important research topic. The main reason is huge economic savings can be achieved when setup times are explicitly included in scheduling decisions in various real-world industrial environments. On the other hand, many real systems commonly face various uncertainties, such as working environment changes, machine breakages, a worker becomes unstable, etc. In such an environment, job-processing times should not be fixed numbers. Motivated by these situations, this article introduces a single-machine scheduling problem with sequence-dependent setup times and scenario-dependent processing times where the objective function is the total completion time. The robust version of this problem without setup times has been shown to be NP hard. To tackle this problem, a lower bound and a dominance rule are derived in a branch-and-bound method for finding an optimal solution. As for determining approximate solutions, five neighborhood schemes are proposed and embedded in the cloud theory-based simulated annealing. Finally, the performances of all proposed algorithms are determined and compared.

Studies on the customer order scheduling problem have been attracting increasing attention. Most current approaches consider that either component processing times for customer orders on each machine are constant or all customer orders are available at the outset of production planning. However, these assumptions do not hold in real-world applications. Uncertainty may be caused by multiple issues including a machine breakdown, the working environment changing, and workers’ instability. On the basis of these factors, we introduced a parallel-machine customer order scheduling problem with two scenario-dependent component processing times, due dates, and ready times. The objective was to identify an appropriate and robust schedule for minimizing the maximum of the sum of weighted numbers of tardy orders among the considered scenarios. To solve this difficult problem, we derived a few dominant properties and a lower bound for determining an optimal solution. Subsequently, we considered three variants of Moore’s algorithm, a genetic algorithm, and a genetic-algorithm-based hyper-heuristic that incorporated the proposed seven low-level heuristics to solve this problem. Finally, the performances of all proposed algorithms were evaluated.