Optimum workforce scheduling under the (14, 21) days-off timetable.
We consider the parallel approximability of two problems arising from high multiplicity scheduling, namely the unweighted model with variable processing requirements and the weighted model with identical processing requirements. These two problems are known to be modelled by a class of quadratic programs that are efficiently solvable in polynomial time. On the parallel setting, both problems are P-complete and hence cannot be efficiently solved in parallel unless P = NC. To deal with the parallel...
We consider the parallel approximability of two problems arising from high multiplicity scheduling, namely the unweighted model with variable processing requirements and the weighted model with identical processing requirements. These two problems are known to be modelled by a class of quadratic programs that are efficiently solvable in polynomial time. On the parallel setting, both problems are P-complete and hence cannot be efficiently solved in parallel unless P = NC. To deal with the parallel...
This paper is concerned with scheduling when the data are not fully known before the execution. In that case computing a complete schedule off-line with estimated data may lead to poor performances. Some flexibility must be added to the scheduling process. We propose to start from a partial schedule and to postpone the complete scheduling until execution, thus introducing what we call a stabilization scheme. This is applied to the m machine problem with communication delays: in our model an estimation...
This paper is concerned with scheduling when the data are not fully known before the execution. In that case computing a complete schedule off-line with estimated data may lead to poor performances. Some flexibility must be added to the scheduling process. We propose to start from a partial schedule and to postpone the complete scheduling until execution, thus introducing what we call a stabilization scheme. This is applied to the m machine problem with communication delays: in our model an estimation...
We propose a parallel algorithm which uses both Monte-Carlo and quasi-Monte-Carlo methods. A detailed analysis of this algorithm, followed by examples, shows that the estimator's efficiency is a linear function of the processor number. As a concrete application example, we evaluate performance measures of a multi-class queueing network in steady state.