RASON: A new approach to the scheduling radiotherapy problem that considers the current waiting times

Scheduling Radiotherapy treatments for cancer patient is a major concern for hospital and clinics. The main problem consists in minimizing the patient waiting time in order to maximize the treatment effectiveness. Most of the modern scheduling approaches use expert systems based on scheduling heuristics and algorithms to develop detailed schedules, in order to efficiently map the patients requirements to the treatment capacity of the health center. In this paper, we propose RASON, a new heuristic based scheduling algorithm for radiotherapy treatments, which main objective is to minimize the average waiting time for each patient. In contrast to well-known existing approaches, our solution manages a priority list that can be dynamically updated according to both the patient category and his/her current waiting time. The generated schedule also impacts the minimization of the average tardiness of the first treatment sessions for each patient. We have evaluated our algorithm using both real data from the Institute of Radiotherapy in Santiago, Chilean and artificial cases generated with a self-developed generator called GeneRa. GeneRa is able to generate cases according to particular constraints inherent to several countries like UK, France and Italy. We show in our proposal evaluation that an on-the-fly scheduling has a great positive impact, allowing to reduce the average waiting time and tardiness for all patients categories. Our algorithm outperforms the JIT and ASAP well-known approaches, with a 95% statistical significance. Our scheduling algorithm allows to significantly reduce the treatment waiting time for different categories of patients. This is a major improvement for the patients as time and delays are crucial parameters to achieve the best effectiveness in cancer treatments.     

An Integrated Technique for Task Matching and Scheduling onto Distributed Heterogeneous Computing Systems

This paper presents a problem-space genetic algorithm (PSGA)-based technique for efficient matching and scheduling of an application program that can be represented by a directed acyclic graph, onto a mixed-machine distributed heterogeneous computing (DHC) system. PSGA is an evolutionary technique that combines the search capability of genetic algorithms with a known fast problem-specific heuristic to provide the best-possible solution to a problem in an efficient manner as compared to other probabilistic techniques. The goal of the algorithm is to reduce the overall completion time through proper task matching, task scheduling, and inter-machine data transfer scheduling in an integrated fashion. The algorithm is based on a new evolutionary technique that embeds a known problem-specific fast heuristic into genetic algorithms (GAs). The algorithm is robust in the sense that it explores a large and complex solution space in smaller CPU time and uses less memory space as compared to traditional GAs. Consequently, the proposed technique schedules an application program with a comparable schedule length in a very short CPU time, as compared to GA-based heuristics. The paper includes a performance comparison showing the viability and effectiveness of the proposed technique through comparison with existing GA-based techniques.     

DAG任务图的一种调度算法

并行程序的调度技术是开发并行计算机系统的计算潜能的关键问题。本文讨论了4种典型的调度算法的缺陷，提出了一种新的调度算法CPFMBF，它采用的策略是：优先调度关键路径节点，其次调度b-level值大的节点，再次调度节点的关键路径影响度大的节点。对照分析及在几种具代表性的工程应用任务图上的实验结果证明CPFMBF算法的调度性能普遍好于其它算法。     

Solving a timetabling problem using hybrid genetic algorithms

All over the world, human resources are used on all kinds of different scheduling problems, many of which are time-consuming and tedious. Scheduling tools are thus very welcome. This paper presents a research project, where Genetic Algorithms (GAs) are used as the basis for solving a timetabling problem concerning medical doctors attached to an emergency service. All the doctors express personal preferences, thereby making the scheduling rather difficult. In its natural form, the timetabling problem for the emergency service is stated as a number of constraints to be fulfilled. For this reason, it was decided to compare the strength of a Co-evolutionary Constraint Satisfaction (CCS) technique with that of two other GA approaches. Distributed GAs and a simple special-purpose hill climber were introduced, to improve the performance of the three algorithms. Finally, the performance of the GAs was compared with that of some standard, nonGA approaches. The distributed hybrid GAs were by far the most successful, and one of these hybrid algorithms is currently used for solving the timetabling problem at the emergency service. © 1997 John Wiley & Sons, Ltd.     

A hybrid simulation and genetic algorithm approach to determine the optimal scheduling templates for open access clinics admitting walk-in patients

With the pressing demand for improving patient accessibility, the traditional scheduling system may not be effective for mitigating the adverse effects caused by no-shows, appointment cancellations and late arrivals. For this reason, open access scheduling, which specifies that a portion of clinic appointment slots be reserved for short-notice appointments, was proposed and adopted in recent years. In literature, many studies have developed a variety of approaches and models to optimize the open access scheduling systems, while few considers the inclusion of walk-in patients and the optimal allocation of reserved slots on the scheduling template under the open access configuration. In this paper, we propose a Discrete Event Simulation and Genetic Algorithm (DES–GA) approach to find the heuristic optimal scheduling template under the clinic setting that allows both open access and walk-in patients. The solution can provide scheduling templates consisting of not only the optimal number of reservations for open access appointments and walk-ins, but also the optimized allocation of these reserved slots, by minimizing the average cost per admission of open access or walk-in patient. In this approach, the cost is measured by the weighted summation of patient waiting time, provider idle time, and provider overtime. A case study and sensitivity analysis are conducted to show how the heuristic optimal scheduling template generated from the proposed approach could vary under different scenarios. This also illustrates the viability of our model. The results show that the heuristic optimal scheduling templates are significantly affected by the patient attendance rate, level of demands of same-day appointment and walk-in admissions, as well as the cost coefficients associated with patient waiting time, provider idle time and provider overtime.     

Combination of data replication and scheduling algorithm for improving data availability in Data Grids

Data Grid is a geographically distributed environment that deals with large-scale data-intensive applications. Effective scheduling in Grid can reduce the amount of data transferred among nodes by submitting a job to a node, where most of the requested data files are available. Data replication is another key optimization technique for reducing access latency and managing large data by storing data in a wisely manner. In this paper two algorithms are proposed, first a novel job scheduling algorithm called Combined Scheduling Strategy (CSS) that uses hierarchical scheduling to reduce the search time for an appropriate computing node. It considers the number of jobs waiting in queue, the location of required data for the job and the computing capacity of sites. Second a dynamic data replication strategy, called the Modified Dynamic Hierarchical Replication Algorithm (MDHRA) that improves file access time. This strategy is an enhanced version of Dynamic Hierarchical Replication (DHR) strategy. Data replication should be used wisely because the storage capacity of each Grid site is limited. Thus, it is important to design an effective strategy for the replication replacement. MDHRA replaces replicas based on the last time the replica was requested, number of access, and size of replica. It selects the best replica location from among the many replicas based on response time that can be determined by considering the data transfer time, the storage access latency, the replica requests that waiting in the storage queue and the distance between nodes. The simulation results demonstrate the proposed replication and scheduling strategies give better performance compared to the other algorithms.     

Single facility scheduling with nonlinear processing times

This paper considers the static single facility scheduling problem where the processing times of jobs are a monotonically increasing function of their starting (waiting) times and the objective is to minimize the total elapsed time (called the makespan) in which all jobs complete their processing. Based on the combinatorial analysis of the problem, an exact optimization algorithm is developed for the general processing time function which is then specialized for the linear case. In view of the excessive computational burden of the exact optimization algorithm for the nonlinear processing time functions, heuristic algorithms are proposed. The effectiveness of these proposed alogrithms is empirically evaluated and found to indicate that these heuristic algorithms yield optimal or near optimal schedules in many cases.     

Intelligent timetable evaluation using fuzzy AHP

There is a substantial body of empirical literature that establishes the benefits of customer satisfaction for enterprises. Among different available options to present our service, selecting the best choice in the customers’ eyes is a vital decision.Developing appropriate passenger train schedules is counted as one of the major managerial concerns in transportation environment. Although different algorithms have been developed to create predictive schedules for a fleet of passenger trains using different performance indicators, selecting the best one embraces some ambiguities and uncertainties. That is because a one-dimensional objective function may not be sufficient for responding customer concerns.The main objective of this paper is to propose an approach within the fuzzy AHP framework for tackling the complexity of multidimensional service evaluations, where “sum of weighted waiting times”, “average of unit waiting time” and “maximum ratio of waiting time to journey time” of a schedule are evaluated and the ultimate judgment on goodness of the schedule is made via the aggregation of the performance measures used. The study is based on the knowledge of certain managers and experts in IRC (Iran Railways Corporation) who are aware of available complexities in train scheduling and have been dealing with customers for several years.     

Compaction of Schedules and a Two-Stage Approach for Duplication-Based DAG Scheduling

Many DAG scheduling algorithms generate schedules that require prohibitively large number of processors. To address this problem, we propose a generic algorithm, SC, to minimize the processor requirement of any given valid schedule. SC preserves the schedule length of the original schedule and reduces processor count by merging processor schedules and removing redundant duplicate tasks. To the best of our knowledge, this is the first algorithm to address this highly unexplored aspect of DAG scheduling. On average, SC reduced the processor requirement 91, 82, and 72 percent for schedules generated by PLW, TCSD, and CPFD algorithms, respectively. SC algorithm has a low complexity (O{N}³) compared to most duplication-based algorithms. Moreover, it decouples processor economization from schedule length minimization problem. To take advantage of these features of SC, we also propose a scheduling algorithm SDS, having the same time complexity as SC. Our experiments demonstrate that schedules generated by SDS are only 3 percent longer than CPFD (O{N}⁴), one of the best algorithms in that respect. SDS and SC together form a two-stage scheduling algorithm that produces schedules with high quality and low processor requirement, and has lower complexity than the comparable algorithms that produce similar high-quality results.     

多约束条件下生产排程智能优化技术

针对当前企业智能化生产中,多条工艺路线共享工序以及工单在生产过程中具有多个约束条件(如工期、优先级、产量等)的问题,提出了一种以"等待时间最短"为主的生产排程智能优化算法.综合考虑工单优先级、工期长短和紧急任务插单等因素,通过一种递归算法来计算工单等待时间,以最小化工单完成时间、最大化资源利用率为优化目标,建立了多约束...     

Dynamic hard-real-time scheduling using genetic algorithm for multiprocessor task with resource and timing constraints

Most publications in shop scheduling area focus on the static scheduling problems and seldom take into account the dynamic disturbances such as machine breakdown or new job arrivals. Motivated by the computational complexity of the scheduling problems, genetic algorithms (GAs) have been applied to improve both the efficiency and the effectiveness for NP-hard optimization problems. However, a pure GA-based approach tends to generate illegal schedules due to the crossover and the mutation operators. It is often the case that the gene expression or the genetic operators need to be specially tailored to fit the problem domain or some other schemes may be combined to solve the scheduling problems. This study presents a GA-based approach combined with a feasible energy function for multiprocessor scheduling problems with resource and timing constraints in dynamic real-time scheduling. Moreover, an easy-understood genotype is designed to generate legal schedules. The results of the experiments demonstrate that the proposed approach performs rapid convergence to address its applicability and generate good-quality schedules.     

基于动态等待时间阈值的延迟调度算法

针对已有的延迟调度算法存在的两个问题,即建立在节点会很快空闲的理论假设下有一定限制,当节点不会很快空闲时算法性能严重下降和基于静态的等待时间阈值不能适应云计算数据中心动态的负载变化及不同用户作业的需求,提出了一种基于动态等待时间阈值的延迟调度算法(dynamic waiting time delay scheduling,DWTDS)。该算法通过给无本地数据节点设置节点最大等待时间,以适应节点不会很快空闲的情况;通过分析数据中心各动态参数,根据概率模型调整作业的等待时间阈值。实验验证该算法在响应时间及负载均衡性方面优于已有的延迟调度算法。     

Generation of optimal schedules for metro lines using model predictive control

This paper presents a new methodology for computation of optimal train schedules in metro lines using a linear-programming-based model predictive control formulation. The train traffic model is comprised of dynamic equations describing the evolution of train headways and train passenger loads along the metro line, considering the time variation of the passenger demand and all relevant safety and operational constraints for practical use of the generated schedule. The performance index is a weighted sum of convex piecewise-linear functions for directly or indirectly modelling the waiting time of passengers at stations, onboard passenger comfort, train trip duration and number of trains in service. The proposed methodology is computationally very efficient and can generate optimal schedules for a whole day operation as well as schedules for transition between two separate time periods with known schedules. The use and performance of the proposed methodology is illustrated by an application to a metro line similar to the North-South line of São Paulo Underground.     

Adaptive Scheduling of Computations and Communications on Distributed-Memory Systems

Compile-time scheduling is one approach to extract parallelism which has proved effective when the execution behavior is predictable. Unfortunately, the performance of most priority-based scheduling algorithms is computation dependent. Scheduling based on the concept of earliest-startable-task produces reasonably short schedules only when available parallelism is large enough to cover the communications. A priority-based decision is more effective when parallelism is low. We propose a scheduling in which the decision function combines two concepts: (1) task-level as global priority and (2) earliest-task-first as local priority The degree of dominance of one of the above concepts is controlled by a computation profile factor that is the ratio of task parallelism to communication. It is shown that the above factor is an upper bound on the deviation of schedule length from optimum. To tune the solution finish time the above scheduler is iteratively applied on the computation graph. In each iteration, the newly generated schedule is used to sharpen the task-levels which contribute in finding shorter schedules in the next iteration. Evaluation is carried out for a wide category of computation graphs with communications for which optimum schedules are known. It is found that pure local scheduling and static priority-based scheduling significantly deviate from the optimum under specific problem instances. Our approach to adapting the scheduling decision to the computation profile is able to produce near-optimum solutions via a much reduced number of iterations than other approaches.     

To Schedule or to Execute: Decision Support and Performance Implications

This paper addresses a fundamental trade-off in dynamic scheduling between the cost of scheduling and the quality of the resulting schedules. The time allocated to scheduling must be controlled explicitly, in order to obtain good-quality schedules in reasonable times. As task constraints are relaxed, the algorithms proposed in this paper increase scheduling complexity to optimize longer and obtain high-quality schedules. When task constraints are tightened, the algorithms adjust scheduling complexity to reduce the adverse effect of long scheduling times on the schedule quality. We show that taking into account the scheduling time is crucial for honoring the deadlines of scheduled tasks. We investigate the performance of our algorithms in two scheduling models: one that allows idle-time intervals to exist in the schedule and another that does not. The model with idle-time intervals has important implications for dynamic scheduling which are discussed in the paper. Experimental evaluation of the proposed algorithms shows that our algorithms outperform other candidate algorithms in several parameter configurations.     

Theoretical proof of edge search strategy applied to power plantstart-up scheduling

Power plant start-up scheduling is aimed at minimizing the start-up time while limiting maximum turbine rotor stresses. This scheduling problem is highly nonlinear and has a number of local optima. In our previous research, we proposed an efficient search model: genetic algorithms (GAs) with enforcement operation to focus the search along the edge of the feasible space where the optimal schedule is supposed to stay. Based on a nonlinear dynamic simulation and a linear inverse calculation with the iteration method, the enforcement operation is applied to move schedules generated by GA toward the edge. We prove that the optimal schedule lies on the edge, ensuring that searching along the edge instead of the entire space can improve the search efficiency significantly without missing the optimum. Furthermore, we provide a theoretical setting equation for the inverse enforcement gains of the linear inverse calculation, intended to move schedules closer to the edge at each iteration of the enforcement operation. The theoretical setting equation is verified and discussed with the test results. We propose the theoretical setting equation with the test results as a guideline for the use of our proposed search model: GA with enforcement operation.     

Lot-sizing and cyclic scheduling for multiple products in a flow shop

This paper considers a production-inventory system in which optimal batch sizes are determined for n products that are processed on m machines in a flow shop. The total cost function for this system is derived by considering three cost components: inventory cost in work-in-process, the final products inventory cost and the machine setup labor cost. In order to make the optimal solution realizable, it is assumed that all products have the same processing cycle time. The capacity constraint considered during the derivation of the optimal lot sizes acts as an additional constraint. Two heuristic algorithms are developed in order to obtain the optimal solution. An important part of these algorithms is the modeling of the recursive relations among the production waiting times and machine idle times. These algorithms are not only used in deriving the optimal solution but also in providing the production schedules. A numerical example is also demonstrated along with the conclusion and indication for future research.     

A two-stage heuristic approach for nurse scheduling problem: A case study in an emergency department

Nurse scheduling is a critical issue in the management of emergency department. Under the intense work environment, it is imperative to make quality nurse schedules in a most cost and time effective way. To this end, a spreadsheet-based two-stage heuristic approach is proposed for the nurse scheduling problem (NSP) in a local emergency department. First, an initial schedule satisfying all hard constraints is generated by the simple shift assignment heuristic. Second, the sequential local search algorithm is employed to improve the initial schedules by taking soft constraints (nurse preferences) into account. The proposed approach is benchmarked with the existing approach and 0–1 programming. The contribution of this paper is twofold. First, it is one of a few studies in nurse scheduling literature using heuristic approach to generate nurse schedules based on Excel spreadsheet. Therefore, users with little knowledge on linear programming and computer sciences can operate and change the scheduling algorithms easily. Second, while most studies on nurse scheduling are situated in hospitals, this paper attempts to bridge the research gap by investigating the NSP in the emergency department where the scheduling rules are much more restrictive due to the intense and dynamic work environment. Overall, our approach generates satisfactory schedules with higher level of user-friendliness, efficiency, and flexibility of rescheduling as compared to both the existing approach and 0–1 programming.     

Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability

This article considers the unrelated parallel machine scheduling problem with sequence- and machine-dependent setup times and machine-dependent processing times. Furthermore, the machine has a production availability constraint to each job. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines to minimize the total completion time. To solve the problem, a mathematical model for the optimal solution is derived, and hybrid genetic algorithms with three dispatching rules are proposed for large-sized problems. To assess the performance of the algorithms, computational experiments are conducted and evaluated using several randomly generated examples.     

一种基于遗传算法的分布式系统的任务调度

一般而言,分布式多处理机上的任意任务图的调度问题即使做了简化假设后依然是NP完全的。遗传算法被证明是解决任务调度等组合问题的有效工具。对现有文献中的关于调度问题的遗传算法进行研究和比较后,该文提出了一种基于遗传算法的任务调度方法,在算法中设计了一种与其他算法不同的变异算子。