查看更多>>摘要：This paper considers a recoverable robust single-machine scheduling problem under polyhedral uncertainty with the objective of minimising the total flow time. In this setting, a decision-maker must determine a first-stage schedule subject to the uncertain job processing times. Then following the realisation of these processing times, they have the option to swap the positions of up to A disjoint pairs of jobs to obtain a second-stage schedule. We first formulate this scheduling problem using a general recoverable robust framework, before we examine the incremental subproblem in further detail. We prove a general result for max-weight matching problems, showing that for edge weights of a specific form, the matching polytope can be fully characterised by polynomially many constraints. We use this result to derive a matching-based compact formulation for the full problem. Further analysis of the incremental problem leads to an additional assignment-based compact formulation. Computational results on budgeted uncertainty sets compare the relative strengths of the three compact models we propose.
查看更多>>摘要：Multi-skilled project scheduling concerns the assignment of multi-skilled resources to activities and the scheduling of these activities in order to minimise the project makespan. Since the resources in these problems can be discerned based on their mastered categorical skills, they are considered to be individual entities (human beings) rather than a general class or type of resources. Therefore, researchers have been looking into multi-skilled resources to investigate which other characteristics differentiate them from one another. A main line of research in the last years studies the incorporation of hierarchical skills and their impact on the decision-making in scheduling problems. Hierarchical skills indicate the level at which resources can perform their different skills. In this paper, we present six multi-skilled resource-constrained project scheduling problems with hierarchical skills. In each of these problems, the hierarchical skills have a different impact on the project and its objectives. Solutions are constructed using a solution framework where new problem-specific local searches are embedded in a genetic algorithm. This new framework is tested on existing data from the literature. Computational experiments compare the quality of the solution approaches and the local searches to an integer programming solver. Furthermore, the principal features and tendencies of each problem are discussed. Finally, best-known solutions and lower bounds for all presented problems will be provided.
查看更多>>摘要：Scheduling a construction project is a complex procedure since it entails several sequences of various jobs or activities that need to be finished within the allotted time frame. Additionally, identifying the factors that influence the construction schedule, such as the nature of construction operations, their duration, dependence relationships, and related probabilities of occurrence, presents challenges and ambiguities. Major construction projects have traditionally been scheduled using conventional project scheduling techniques, such as the programme evaluation and review technique (PERT) and critical path method (CPM), among others. However, these construction scheduling methods continue to be inadequate for identifying the essential elements needed to generate complete and precise schedules, highlighting the need for a more effective technique to overcome uncertainties and stochastic aspects of construction scheduling. To fully comprehend these inherent stochastic properties, the present study employs the Graphical Evaluation and Review Technique (GERT), a stochastic technique for project network analysis. While prior studies support the effectiveness of GERT in the pre-construction phase, there is a lack of investigation into its practical application within the domain of residential construction. The present investigation addresses this gap by demonstrating the effectiveness of GERT in scheduling real-time residential projects by conducting a systematic and comparative analysis of GERT, PERT, and CPM methodologies across various scales of residential structures. GERT is initially applied to schedule a real-time single-storey residential structure. The GERT schedule closely reflects the as-built schedule of the structure. In addition, GERT is utilised to schedule 45 construction projects in real time, further emphasising its relevance and applicability. The GERT-generated schedule for these projects is validated for correctness by comparing it to the actual project duration. The findings demonstrate the advantages of the proposed technique in comparison to existing methods.
查看更多>>摘要：In recent years, the importance of achieving staffing flexibility to balance supply and demand in unpredictable environments, such as hospitals, has grown. This study focuses on shift design with task rotations for a multi-skilled workforce, specifically in service contexts characterized by pronounced demand variability. We introduce a mathematical programming model designed to identify optimal shift start times with task assignments for both full-time and part-time employees, where workers can rotate between multiple tasks during their shifts. We develop a column generation approach that allows us to solve realistically-sized problem instances. Our analysis, derived from staffing data of a university hospital's radiation oncology department, reveals the model's robust applicability across varying demand landscapes. We demonstrate that incorporating task rotations in the shift design can improve workload balancing when task demands fluctuate considerably. Remarkably, our column generation technique produces optimal integer solutions for realistic problem instances, outperforming the compact mixed-integer formulation which struggles to achieve feasible results. We find that the success of embedding task rotations in shift design decisions is directly influenced by the demand profile, which in turn affects the necessary qualification mix of the workforce.
查看更多>>摘要：The performance of safety-critical systems implemented on multi-core platforms depends heavily on the scheduling mechanism used. This paper addresses the problem of multi-core scheduling of a real-time application modelled as a Directed Acyclic Graph (DAG) with multiple service levels (where, a higher service level implies higher Quality-of-Service (QoS)), by proposing a novel two-phase offline-online scheduling mechanism called HYBRID-SCHED. The offline phase constructs a static schedule assuming worst-case execution behaviour, in order to ensure desired predictability with a minimum guaranteed QoS under all possible execution scenarios. Two alternative offline solution strategies have been designed. While the first strategy is a fast but reasonably good heuristic solution called Service-level Aware Scheduler (SAS), the second is a branch-and-bound based optimal solution-space search technique. However, online execution based on strict adherence to the static schedule may result in poor resource utilization as actual execution time of tasks at run time may be significantly less than worst-case estimates. In order to improve the situation, an online scheduler called Actual Execution-time Aware Scheduler (AEAS) has been developed. The basic goal of AEAS is to strategically reclaim resources that were provided for tasks at design time but are in fact being used inactively at run time. By gradually raising the service levels of the remaining (yet-to-be-completed) jobs, AEAS can then use the recovered resources to improve system-level QoS. Using real-world benchmark applications, we assessed the performance of the suggested framework. Results obtained demonstrate the usefulness of our plan.
NETL
NSTL
Springer Nature