## 6 Designing, Balancing and Scheduling Assembly Lines with Uncertain Parameters
### A Stability Approach to Job-Shop Scheduling Problems with Uncertain Parameters  
In [142; 143; 144], the stability radius of the optimal semi-active schedule for shop scheduling problems was investigated. The developed algorithms can be used to solve a set of uncertain scheduling problems arising in optimization of the assembly and disassembly lines. The authors of these articles present the necessary and sufficient conditions for the existence of a zero-stability radius of the optimal semi-active schedule, as well as formulas for calculating the stability radii in a general case. The uncertain scheduling problem, \(Im||C_{max}\), is studied in [145]. A set of jobs has to be processed on identical machines. Every job may be processed on any available machine without preemptions. The criterion is to minimize the makespan (the completion time of the last job in the schedule). During the realization of a schedule, durations of some jobs may deviate from the initial values estimated before scheduling. Other jobs have fixed durations that are known before scheduling and do not change in the realization of any feasible semi-active schedule. For this uncertain scheduling problem, \(Im||C_{max}\), which is NP-hard even for the simplest deterministic case with \(m=2\), a stability analysis of the optimal semi-active schedule was conducted. The necessary and sufficient conditions for an optimal semi-active schedule were proven to be unstable with respect to infinitely small variations of the non-fixed job durations (in this case, the stability radius of the unstable semi-active schedule is equal to zero). It was shown that the stability radius of an optimal semi-active schedule could be infinitely large. The necessary and sufficient conditions for an infinitely large stability radius were proven. Several lower and upper bounds on the stability radius have been established. A formula was proven, and the algorithm was developed for calculating the exact stability radius in a general case of the uncertain problem, \(Im||C_{max}\). In [146], a two-machine shop scheduling problem was studied, provided that only lower and upper bounds on processing times of the jobs are known before scheduling. An exact value of the job processing time remains unknown until completion of this job. The objective is to minimize the makespan (schedule length). The authors of this paper address the issue of how to best execute a semi-active schedule if the job processing time may take any real value from the given segment. Scheduling decisions consist of two phases: an off-line phase and an online phase. Using available information on the lower bounds and upper bounds for each job processing time that are available in the off-line phase, a scheduler can determine a minimal dominant set of semi-active schedules (DS for short) based on sufficient conditions for a schedule domination. The DS optimally covers all possible scenarios of the uncertain job processing times in the sense that, for each scenario, there is at least one semi-active schedule in the DS which is optimal. The DS enables a scheduler to quickly make an online scheduling decision whenever additional information on completing some jobs is available. A scheduler can choose a semi-active schedule, which is optimal for the most scenarios. An algorithm for testing a set of conditions for schedule dominance was developed. The developed algorithm is polynomial in the number of jobs. Computational experiments have shown the effectiveness of the algorithms. If there were no more than 600 jobs, then all 1000 tested instances in each tested series were solved in 1 s. A problem instance with 10,000 jobs was solved in 0.4 s on average. The most problem instances from nine tested problem classes were optimally solved. If the maximum relative error of the job processing time was not greater than 20%, then more than 80% of the tested instances were optimally solved.