We address a manufacturing environment with the no-wait constraint which is common in industries such as metal, plastic, and semiconductor. Setup times are modelled as uncertain with the objective of minimizing maximum lateness which is an important performance measure for customer satisfaction. This problem has been addressed in scheduling literature for the two-machine no-wait flowshop where dominance relations were presented. Recently, another dominance relation was presented and shown to be about 90% more efficient than the earlier ones. In the current paper, we propose two new dominance relations, which are less restrictive than the earlier ones in the literature. The new dominance relations are shown to be 140% more efficient than the most recent one in the literature. As the level of uncertainty increases, the newly proposed dominance relation performs better, which is another strength of the newly proposed dominance relation. Moreover, we also propose constructive heuristics and show that the best of the newly proposed heuristics is 95% more efficient than the existing one in the literature under the same CPU time.

We consider a no-wait m-machine flowshop scheduling problem which is common in different manufacturing industries such as steel, pharmaceutical, and chemical. The objective is to minimize total tardiness since it minimizes penalty costs and loss of customer goodwill. We also consider the performance measure of total completion time which is significant in environments where reducing holding cost is important. We consider both performance measures with the objective of minimizing total tardiness subject to the constraint that total completion time is bounded. Given that the problem is NP-hard, we propose an algorithm. We conduct extensive computational experiments to compare the performance of the proposed algorithm with those of three well performing benchmark algorithms in the literature. Computational results indicate that the proposed algorithm reduces the error of the best existing benchmark algorithm by 88% under the same CPU times. The results are confirmed by extensive statistical analysis. Specifically, ANOVA analysis is conducted to justify the difference between the performances of the algorithms, and a test of hypothesis is performed to justify that the proposed algorithm is significantly better than the best existing benchmark algorithm with a significance level of 0.01.

Scheduling plays an important role in service and manufacturing environments for the delivery of reliable products on time. The scheduling literature reveals that the vast majority of the investigated scheduling problems are for the deterministic case where all parameters of jobs are known in advance and are fixed. However, in some real-world environments, the assumption of fixed parameters of jobs is not valid since job parameters are uncertain. An uncertain parameter can be modelled as having a probability distribution, or it can be modelled as a fuzzy number, or it can be modelled as a random variable within some interval with lower and upper bounds, distribution free. If the uncertain parameter, e.g., processing time, is modelled as a random variable within some lower or upper bounds, it is called interval or bounded processing time. The objective of this paper is to survey the investigated scheduling problems with interval or bounded processing/setup times. The scheduling literature is reviewed, the addressed problems are analyzed, and classified based on shop environments (single machine, parallel machine, flowshop, job shop), performance measures, the approach taken in the papers to solve the considered problem, and interval/bounded processing times or setup times. Some future research opportunities with interval/bounded processing/setup times are presented.