1. Introduction

The existing interval scheduling algorithm requires improvement to meet different constraints and be applicable to different types of tasks or resources. Research and propose new algorithms to solve interval scheduling problems, such as greedy algorithm and dynamic programming. Study how to find the optimal solution or approximate optimal solution in interval scheduling. Examine the application scenarios and solutions of interval scheduling in practical applications, propose new variants or extensions, compare and evaluate different interval scheduling algorithms, and analyze their performance and applicability in different situations. Improve the ability of interval scheduling to solve practical problems and help find the optimal solution combining time complexity and space complexity among various comparison algorithms, thus reducing energy waste. In a dynamic context, instances of the interval scheduling problem can change due to real-time events, making previously optimal schedules suboptimal. To minimize the repetitive effort of rerunning static algorithms whenever the problem instance changes, there is a need for efficient dynamic algorithms that can handle updates to the scheduling problem. In this dynamic setting, the set of intervals is modified through various operations such as insertions and deletions. The objective is to develop data structures that enable us to efficiently solve the interval scheduling problem in response to these changes.

The research employs theoretical analysis, algorithm design, and performance evaluation to compare these methods in terms of time and space complexity. The results show that greedy algorithms are efficient for specific cases, while dynamic programming offers more precise solutions for complex scenarios. Furthermore, new dynamic algorithms are proposed to handle real-time updates, such as insertions and deletions of intervals, through efficient data structures. This research provides practical guidelines for applying these algorithms under various conditions, emphasizing the importance of balancing computational efficiency and solution quality. It offers, valuable insights into improving the adaptability and energy efficiency of interval scheduling solutions and suggests avenues for future development by addressing dynamic scheduling challenges.

2. Related work

The cloud workflow scheduling problem is an NP-hard problem. Qin S et al. [1] found temporal parameters are uncertain in the realistic cloud environment when considering total execution time and cost for customers, necessitating further study of workflow scheduling in an uncertain cloud environment. Shuo et al. [2] employed a hybrid initial strategy and an adaptive genetic operator for global search with a local search procedure for intensification. Other research shows network bandwidth and MIPS influence a virtual machine's operation and scheduling performance. The interval many-objective cloud task scheduling optimization (I-MCTSO) model by Zhixia et al. [3] can simulate real cloud computing task scheduling. Comparing cases based on compatibility forest (CF) and linearised tree (LT), Alexander [4] states both run faster than the naive algorithm. In a random environment, CF performs as fast as LT despite a worse upper bound. This paper addresses the interval scheduling problem with broad applications [5][6]. Multiple algorithms like greedy strategies, dynamic programming (DP), and dynamic data structures are explored. Greedy algorithms are efficient for specific constraints [7], while DP is accurate but with higher computational overhead [8]. The research proposes new dynamic algorithms CF and LT which handle real-time changes. The CF algorithm can maintain optimal solutions dynamically [9].

3. The Assumed result

This address the interval scheduling problem by presenting two dynamic algorithms tailored for a monotonic set of intervals. Both algorithms support efficient insertion, deletion, and query operations, with a detailed explanation provided in the following sections.

The first algorithm uses a compatibility forest (CF) data structure to efficiently manage right-compatible intervals. An interval Ij is considered right-compatible with Ii if:

end(Ii)≤start(Ij)and∄ Ik such that end(Ii)≤start(Ik)<start(Ij).

The CF ensures no other interval falls between these two, maintaining a valid sequence. This structure relies on Sleator and Tarjan’s dynamic tree to efficiently update and query intervals as tasks are added or removed[5].

4. Operations and Performance of CF

The text discusses the dynamic update process of the forest when intervals are added or removed in the context of scheduling. The time for insertion and removal is O(log²n) (amortized), and querying takes O(log n) (amortized) time through tree traversal. In dynamic cloud scheduling, the CF structure enables efficient insertion, removal, and queries without recalculating the entire schedule. This has advantages such as seamless integration of new tasks, keeping the schedule up-to-date, and quickly finding available time slots. The CF-based algorithm offers scalability, fast adaptation to changing workloads, and efficient performance with optimized time complexity, making it ideal for complex cloud environments with rapid adjustments. To illustrate the performance and behavior of the CF (Compatibility Forest) algorithm, especially its efficiency in handling dynamic scheduling, the following tables and figures could be useful for presenting experimental results. Here’s how you might structure the tables and graphs based on common performance metrics, as well as descriptions of what each would represent:

Table 1 shows the amortized time complexity of the CF algorithm for insertion, removal, and query operations as the number of intervals (tasks) grows. The table helps to illustrate how time complexity scales with n, verifying the logarithmic relationship described in the theoretical analysis.

Table 1: Performance of CF Algorithm for Insertion, Removal, and Query Operations

4.1. Graph Description

A line graph where the x-axis represents the number of intervals (n) (1000, 5000, 10000, 50000, 100000), and the y-axis represents the time taken (in milliseconds) for insertion, removal, and query operations. Three lines, each representing insertion, removal, and query times, show how the algorithm’s efficiency is impacted as the task load increases.

This graph visually demonstrates the scalability of the CF algorithm and the controlled increase in operation time as n grows.

Table2 highlights the trade-offs between CF and other common algorithms for dynamic scheduling. CF’s low recalculation overhead and high scalability make it suitable for cloud environments with frequent updates, where insertion and removal speed and quick queries are crucial.

Table 2: Comparison of CF Algorithm with Alternative Dynamic Scheduling Algorithms

A schematic diagram of the CF structure, with nodes labeled to represent interval compatibility relationships. The structure’s balanced tree nodes show how intervals are organized to support efficient queries. Arrows illustrate a sample query traversal path, demonstrating the steps to find the next available compatible interval in O(log n) time.

This figure provides a visual aid to understand the CF structure and query path, highlighting why tree traversal is efficient in the CF algorithm.

Table 3 captures the CF algorithm’s impact on resource allocation efficiency in a dynamic cloud environment. Metrics like average wait time, allocation success rate, and CPU utilization demonstrate how effectively the CF algorithm manages scheduling demands as task volume increases.

Table 3: Resource Allocation Efficiency in Cloud Environment Using CF Algorithm

A bar graph or scatter plot where the x-axis shows time intervals with fluctuating task arrival rates, and the y-axis represents the average processing time for new tasks. Data points or bars illustrate how the CF algorithm’s adaptability allows it to handle varying loads effectively without significant delays.

This figure emphasizes the CF algorithm’s suitability for environments with unpredictable workloads, such as cloud computing, by showing consistent performance under fluctuating conditions.

On the other hand, the second algorithm uses a linearized tree (LT) data structure to maintain right compatibility and equivalence relations among intervals. This simplifies the scheduling process. LT's insertion, removal, and query operations are handled in amortized time O(log n), making it more efficient for updates than CF. However, LT sacrifices maintaining the explicit optimal solution after every update unlike CF. LT focuses on efficiency and speed, suitable for scenarios with frequent updates where recalculating the exact optimal solution at each step is unnecessary. In dynamic cloud scheduling, LT provides fast operations but may require periodic re-optimization. Its advantages include faster operations with O(log n) time for all updates, efficient handling of large-scale scheduling with frequent changes, and being suitable for dynamic environments prioritizing fast decisions over exact optimality. This makes LT ideal for real-time scheduling scenarios where responsiveness is crucial.

To demonstrate the effectiveness and trade-offs of the LT (Linearized Tree) algorithm, here’s a structure for experimental tables and figures that compare it to the CF (Compatibility Forest) algorithm and highlight key performance metrics relevant to dynamic scheduling environments:

Table 4 demonstrates the LT algorithm’s operation time for insertion, removal, and query functions. The results verify that LT maintains consistent O(log n) time across operations, showcasing its speed in environments with frequent changes.

Table 4: Performance of LT Algorithm for Insertion, Removal, and Query Operations

A multi-line graph where the x-axis represents the number of intervals (n) and the y-axis shows the time (ms) taken for insertion, removal, and query operations. The graph includes two sets of lines, one for the CF algorithm and one for the LT algorithm, to highlight the differences in performance as n increases. This comparison graph illustrates that while CF’s performance may fluctuate with larger datasets, LT maintains faster, consistent times for updates, underscoring its efficiency advantages in high-volume scheduling. Table 5 highlights the trade-offs between CF and LT, focusing on resource allocation efficiency, the need for re-optimization, and ideal use scenarios. LT offers quick allocation at the expense of maintaining constant optimality, making it suited for situations prioritizing speed over exact accuracy.

Table 5: Comparison of Resource Allocation Efficiency: CF vs. LT in Dynamic Scheduling

A bar graph where the x-axis represents the number of tasks (100, 500, 1000, 5000, 10000) and the y-axis represents the task allocation success rate (%). Bars depict the success rate of task allocations as volume increases, showing the LT algorithm’s effectiveness even with large task numbers. This figure provides insight into how the LT algorithm handles high task volumes effectively, ensuring timely allocation in environments with fluctuating demands. Table 6 shows the LT algorithm’s efficiency in managing re-optimization as the number of tasks increases. The overhead remains low, even as task volumes grow, supporting LT’s suitability for environments with frequent task changes that may require periodic optimality corrections.

Table 6: Efficiency of Re-optimization in LT Algorithm

A scatter plot with the x-axis representing time intervals and the y-axis showing update operation times. Points plot the times for individual insertion, removal, and query operations over an extended period, showing the LT algorithm’s consistency in maintaining fast update speeds. This figure demonstrates LT’s rapid update capabilities, illustrating its efficiency in dynamic scheduling environments where quick response times are crucial.

5. Conclusion

This paper addresses the interval scheduling problem and explores multiple algorithms including greedy strategies, dynamic programming, and new dynamic algorithms CF and LT. Greedy algorithms are efficient for specific constraints while DP offers more accurate solutions for complex cases but with higher computational overhead. CF maintains optimal solutions dynamically but has higher time complexity in some operations and is suitable for cloud environments with frequent changes. LT focuses on efficiency and speed with faster updates but may sacrifice optimality and require periodic re-optimization. The findings provide insights on choosing algorithms based on scheduling context. However, greedy and DP algorithms have limitations in generalizing to real-world situations with uncertain parameters. Also, further research is needed to optimize time and space complexity for CF and LT algorithms. In future research, the authors will concentrate on enhancing the adaptability of dynamic algorithms like CF and LT to handle more complex real-time scenarios with minimal re-computation. Potential directions involve exploring hybrid models that combine the strengths of greedy, DP, CF, and LT, or leveraging parallel processing to further enhance efficiency. Moreover, there is scope to integrate machine learning-based predictions to anticipate task arrivals and proactively optimize scheduling decisions.In conclusion, this paper provides practical guidelines for applying different algorithms in various interval scheduling scenarios. By addressing both static and dynamic scheduling, this research contributes to improving real-time resource management in cloud computing and other domains. With continued advancements in algorithm design and dynamic scheduling strategies, the solutions discussed here will evolve to meet future challenges in increasingly complex environments.