Sequencing with uncertain numerical data for makespan minimisation

We consider a scheduling problem with the objective of minimising the makes pan under uncertain numerical input data (for example, the processing time of an operation, the job release time and due date) and fixed structural in put data (for example the precedence and capacity constraints). We assume t hat at (before) the scheduling stage the structural input data are known an d fixed but all we know about the numerical input data are their upper and lower bounds, where the uncertain numerical data become realised at the con trol stage as the scheduled process evolves. After improving the mixed grap h model, we present an approach for dealing with our scheduling problem und er uncertain numerical data based on a stability analysis of an optimal mak espan schedule. In particular, we investigate the candidate set of the crit ical paths in a circuit-free digraph, characterise a minimal set of the opt imal schedules, and develop an optimal and a heuristic algorithm. We also r eport computational results for randomly generated as well as well-known te st problems.