In this paper, we study an NP-hard problem of a single machine scheduling minimizing the makespan, where the mixed-critical tasks with an uncertain processing time are scheduled. We show the derivation of F-shaped tasks from the probability distribution function of the processing time, then we study the structure of problems with two and three criticality levels for which we propose efficient exact algorithms and we present computational experiments for instances with up to 200 tasks. Moreover, we show that the considered problem is approximable within a constant multiplicative factor.
The concept of match-up scheduling was introduced by @cite_0 . In a case of a disruption, the goal is to construct a new schedule that matches the original one at some point in the future. This concept is mostly studied in the context of manufacturing problems @cite_5 .
@cite_0 @cite_5
2058056324 2145151750
This paper considers the rescheduling of operations with release dates and multiple resources when disruptions prevent the use of a preplanned schedule. The overall strategy is to follow the preschedule until a disruption occurs. After a disruption, part of the schedule is reconstructed to match up with the preschedule at some future time. Conditions are given for the optimality of this approach. A practical implementation is compared with the alternatives of preplanned static scheduling and myopic dynamic scheduling. A set of practical test problems demonstrates the advantages of the matchup approach. We also explore the solution of the matchup scheduling problem and show the advantages of an integer programming approach for allocating resources to jobs. Abstract This paper addresses the problem of updating a machine schedule when either a random or an anticipated disruption occurs after a subset of the jobs has been processed. In such cases, continuing with the original schedule is likely to be suboptimal and may not even be feasible. The approach taken here differs from most rescheduling analysis in that the cost associated with the deviation between the original and the new schedule is included in the model. We concentrate on cases in which the shortest processing time (SPT) rule is optimal for the original problem. Both single and parallel two-machine environments are considered.