An activity-list-based nested partitions algorithm for resource-constrained project scheduling

The resource-constrained project scheduling problem (RCPSP) has received wide attention. In this paper, an activity-list-based nested partitions algorithm (ALNP) is developed for solving the RCPSP and a P-ALNP is proposed to improve ALNP with local adjustment. In the algorithms, to improve the search efficiency, a partial double justification is employed as local search mechanism. The computational experiments on the PSPLIB and analysis on robustness of the algorithms show that ALNP outperforms the traditional serial scheduling scheme for solving the large-scale, complex RCPSPs, and P-ALNP can improve ALNP and obtain better results. P-ALNP is a competitive algorithm for solving the RCPSP.     

An improved exact algorithm for single-machine scheduling to minimise the number of tardy jobs with periodic maintenance

In this paper, we investigate a single-machine scheduling problem with periodic maintenance, which is motivated by various industrial applications (e.g. tool changes). The pursued objective is to minimise the number of tardy jobs, because it is one of the important criteria for the manufacturers to avoid the loss of customers. The strong NP-hardness of the problem is shown. To improve the state-of-the-art exact algorithm, we devise a new branch-and-bound algorithm based on an efficient lower bounding procedure and several new dominance properties. Numerical experiments are conducted to demonstrate the efficiency of our exact algorithm.     

Hybrid genetic algorithm for bi-objective resource-constrained project scheduling

In this study, we considered a bi-objective, multi-project, multi-mode resource-constrained project scheduling problem. We adopted three objective pairs as combinations of the net present value (NPV) as a financial performance measure with one of the time-based performance measures, namely, makespan (C_max), mean completion time (MCT), and mean flow time (MFT) (i.e., minC_max/maxNPV, minMCT/maxNPV, and minMFT/maxNPV). We developed a hybrid non-dominated sorting genetic algorithm II (hybrid-NSGA-II) as a solution method by introducing a backward–forward pass (BFP) procedure and an injection procedure into NSGA-II. The BFP was proposed for new population generation and post-processing. Then, an injection procedure was introduced to increase diversity. The BFP and injection procedures led to improved objective functional values. The injection procedure generated a significantly high number of non-dominated solutions, thereby resulting in great diversity. An extensive computational study was performed. Results showed that hybrid-NSGA-II surpassed NSGA-II in terms of the performance metrics hypervolume, maximum spread, and the number of non-dominated solutions. Solutions were obtained for the objective pairs using hybrid-NSGA-II and three different test problem sets with specific properties. Further analysis was performed by employing cash balance, which was another financial performance measure of practical importance. Several managerial insights and extensions for further research were presented.     

An algorithm for scheduling parallel processors

This paper deals with optimal scheduling of jobs on identical parallel processors. The paper develops an algorithm for determining the optimal schedule and gives a proof of the algorithm. The criterion used is that of minimizing the total cost for processing all jobs when the jobs are assigned non-decreasing waiting costs which are non-linear. Extension of the algorithm for jobs with due dates is also given. Computational results are given which indicate the effectiveness of the algorithm as compared to complete enumeration.     

An optimization-based algorithm for job shop scheduling

Scheduling is a key factor for manufacturing productivity. Effective scheduling can improve on-time delivery, reduce inventory, cut lead times, and improve the utilization of bottleneck resources. Because of the combinatorial nature of scheduling problems, it is often difficult to find optimal schedules, especially within a limited amount of computation time. Production schedules therefore are usually generated by using heuristics in practice. However, it is very difficult to evaluate the quality of these schedules, and the consistency of performance may also be an issue. In this paper, near-optimal solution methodologies for job shop scheduling are examined. The problem is formulated as integer optimization with a “separable” structure. The requirement of on-time delivery and low work-in-process inventory is modelled as a goal to minimize a weighted part tardiness and earliness penalty function. Lagrangian relaxation is used to decompose the problem into individual part subproblems with intuitive appeal. By iteratively solving these subproblems and updating the Lagrangian multipliers at the high level, near-optimal schedules are obtained with a lower bound provided as a byproduct. This paper reviews a few selected methods for solving subproblems and for updating multipliers. Based on the insights obtained, a new algorithm is presented that combines backward dynamic programming for solving low level subproblems and interleaved conjugate gradient method for solving the high level problem. The new method significantly improves algorithm convergence and solution quality. Numerical testing shows that the method is practical for job shop scheduling in industries. This work was supported in part by the National Science Foundation under DMI-9500037, and the Advanced Technology Center for Precision Manufacturing, University of Connecticut.     

An exact algorithm for generating homogenous two-segment cutting patterns

An exact algorithm is proposed for generating homogenous two-segment patterns for the constrained two-dimensional guillotine-cutting problems of rectangular items. It is a bottom-up approach combined with branch-and-bound techniques. The stock plate is divided into two segments. Each segment consists of strips of the same length and direction. Only homogenous strips are considered, each of which contains items of the same type. The strip directions of the two segments may be either the same or perpendicular to each other. The algorithm uses a tree-search procedure. It starts from an initial lower bound, implicitly generates all possible segments through the assembly of strips, and constructs possible patterns through the combination of two segments. Tighter bounds are established to discard non-promising segments. The computational results indicate that the algorithm is efficient both in computation time and in material utilization, and is able to deal with relatively large-scale problems.     

A novel branch-and-bound algorithm for the chance-constrained resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) has been widely studied during the last few decades. In real-world projects, however, not all information is known in advance and uncertainty is an inevitable part of these projects. The chance-constrained resource-constrained project scheduling problem (CC-RCPSP) has been recently introduced to deal with uncertainty in the RCPSP. In this paper, we propose a branch-and-bound (B&B) algorithm and a mixed integer linear programming (MILP) formulation that solve a sample average approximation of the CC-RCPSP. We introduce two different branching schemes and eight different priority rules for the proposed B&B algorithm. The computational results suggest that the proposed B&B procedure clearly outperforms both a proposed MILP formulation and a branch-and-cut algorithm from the literature.     

An algorithm for exact eigenvalue calculations for rotationally periodic structures

An existing algorithm ensures that no eigenvalues are missed when using the stiffness matrix method of structural analysis, where the eigenvalues are the natural frequencies of undamped free vibration analyses or the critical load factors of buckling problems. The algorithm permits efficient multi-level substructuring and gives ‘exact’ results when the member equations used are those obtained by solving appropriate differential equations. The present paper extends this algorithm to cover rotationally periodic (i.e. cyclically symmetric) three-dimensional structures which are analysed by using complex arithmetic to obtain a stiffness matrix which involves only one of the rotationally repeating portions of the structure. Nodes and members are allowed to coincide with the axis of rotational periodicity and the resulting modes are classified. Rigid body freedoms are accounted for empirically, and the ‘exact’ member equations and efficient multi-level substructuring of the earlier algorithm can be used when assembling the stiffness matrix of the repeating portion.     

Study on constraint scheduling algorithm for job shop problems with multiple constraint machines

This paper focuses on a job-shop scheduling problem with multiple constraint machines (JSPMC). A constraint scheduling method for the JSPMC is proposed. It divides the machines in the shop into constraint and non-constraint machines based on a new identification method, and formulates a reduced problem only for constraint machines while replacing the operations of non-constraint machines with time lags. The constraint machines are scheduled explicitly by solving the reduced problem with an efficient heuristic, while the non-constraint machines are scheduled by the earliest operation due date (EODD) dispatching rule. Extensive computational results indicate that the proposed constraint scheduling algorithm can obtain a better trade-off between solution quality and computation time compared with various versions of the shifting bottleneck (SB) methods for the JSPMC.     

An exact algorithm for preventive maintenance planning of series-parallel systems

Reliability is a meaningful parameter in assessing the performance of systems such as chemical processing facilities, power plant, aircrafts, ships, etc. In the literature, reliability optimization is widely considered during the system design phase and it is carried out by an opportune selection of both system components and redundancy. On the other hand, the problem of maintaining a required level of reliability by an opportune maintenance policy has been poorly examined. The paper tackles this problem for a system whose major components can be maintained only during a planned system downtime. An exact algorithm is proposed in order to single out the set of components that must be maintained to guarantee a required reliability level up to the next planned stop with the minimum cost. In order to verify the algorithm effectiveness, it has been applied to a complex real case regarding ship maintenance.     

Mathematical model and exact algorithm for the home care worker scheduling and routing problem with lunch break requirements

Home health care or home care (HHC/HC) refers to the delivery of social, medical and paramedical services to clients in their own homes. Each day, care workers start from the HHC/HC centre, visit some clients and return to the centre. During the service delivery process, there is usually a lunch break for each worker. In this paper, we address a real-life home care worker scheduling and routing problem with the consideration of lunch break requirements. A three-index mathematical model is constructed for the problem. The problem is decomposed into a master problem and several pricing sub-problems, and is optimally solved by a branch-and-price (B&P) algorithm. Specifically, a sophisticated label-correcting algorithm is designed to address lunch break constraints in pricing sub-problems; some cutting-edge acceleration strategies are applied during the column generation process. Experimental results show that the proposed B&P algorithm is able to produce satisfied solutions within an acceptable runtime and outperforms the mixed integer programming solver CPLEX.     

一种改进的保证混合业务服务质量的跨层调度算法

提出一种改进的基于优先级的IEEE 802.16系统跨层调度算法,该算法综合考虑了媒体接入控制(MAC)层的业务服务质量(QoS)要求与无线信道的时变特性,通过动态调整实时轮询(rtPS)业务的优先级加权系数,在保证rtPS业务QoS要求的前提下,增加非实时轮询(nrtPS)业务和尽力而为(BE)业务的调度机会,提高nrtPS业务和BE业务的传输速率.每个连接分配的优先级根据信道和服务状态进行动态更新,每次调度优先级最高的连接.仿真结果表明,该算法能够为不同业务提供QoS保证,同时有效提高了频谱利用率和系统吞吐量.     

An integrated scheduling algorithm with device dependence deferred constraint

针对目前综合调度中没有考虑设备有关延迟约束(DDC)影响调度效果的问题,提出了存在设备有关延迟约束的综合调度的算法.该算法在标准工序、设备有关延迟工序(DDP)和包含设备有关延迟约束的加工工艺树等概念的基础上,将等待延迟时间转化为设备有关延迟工序,使存在DDC的调度问题转变为较易解决的一般综合调度问题,再用拟关键路径法( ACPM)确定工序的调度次序,最后用前沿贪心规则确定工序的开始时间.为了使设备有关延迟工序影响的工序尽早开始,进一步提出了设备有关延迟工序配合调整的策略.实验表明,该调度算法能够有效解决存在设备有关延迟约束的综合调度问题,可在不提高算法复杂度的前提下,提高调度结果的精度并减少产品总的加工时间.     

An adaptive scheduling algorithm for a parallel machine problem with rework processes

The development of a scheduling methodology for a parallel machine problem with rework processes is presented in this paper. The problem is to make a schedule for parallel machines with rework probabilities, due-dates, and sequence dependent setup times. Two heuristics are developed based on a dispatching algorithm and problem-space-based search method. In order to evaluate the efficacy of the proposed algorithms, six performance indicators are considered: total tardiness, maximum lateness, mean flow-time, mean lateness, the number of tardy jobs, and the number of reworks. This paper shows how these algorithms can adaptively capture the characteristics of manufacturing facilities for enhancing the performance under changing production environments. Extensive experimental results show that the proposed algorithms give very efficient performance in terms of computational time and each objective value.     

An improved harmony search algorithm for emergency inspection scheduling

The ability of nature-inspired search algorithms to efficiently handle combinatorial problems, and their successful implementation in many fields of engineering and applied sciences, have led to the development of new, improved algorithms. In this work, an improved harmony search (IHS) algorithm is presented, while a holistic approach for solving the problem of post-disaster infrastructure management is also proposed. The efficiency of IHS is compared with that of the algorithms of particle swarm optimization, differential evolution, basic harmony search and the pure random search procedure, when solving the districting problem that is the first part of post-disaster infrastructure management. The ant colony optimization algorithm is employed for solving the associated routing problem that constitutes the second part. The comparison is based on the quality of the results obtained, the computational demands and the sensitivity on the algorithmic parameters.     

An efficient task scheduling algorithm for heterogeneous multi-core processors

针对现有异构多核处理器任务调度算法效率低的问题,提出了一种综合性的、高效的静态任务调度算法,即聚簇与复制列表优化调度(CDLOS)算法.该算法首先通过对任务图进行聚簇优化,降低某些特殊任务的通信开销;然后从整个任务图的拓扑结构出发计算任务的优先级权值,提高关键任务的优先级;继而采用区间插入和任务复制技术进行调度,降低处理器资源浪费;最后通过优化调度结果,消除冗余任务,减小整个任务的调度长度.实例分析和模拟实验结果表明:与以往算法相比,此新算法较高地提升了多核处理器任务调度的效率,具有更好的应用前景.     

An exact algorithm dealing with shared signals in the GO methodology

This paper provides an exact quantification algorithm dealing with shared signals in the GO methodology. The exact calculation formulas of the output signal state probability of a logic operator, which includes the input signals with the shared signals, have been derived. All the shared signals should be transferred to the output signal of this logic operator and in the following calculation the formulas are still exact. This exact algorithm permits the direct calculation of all signal state probabilities of the systems. The result of an example shows that the exact algorithm is available and meaningful for more development of the GO methodology, it will be useful for more practical applications.     

An adaptive multi-population genetic algorithm for job-shop scheduling problem

Job-shop scheduling problem (JSP) is a typical NP-hard combinatorial optimization problem and has a broad background for engineering application. Nowadays, the effective approach for JSP is a hot topic in related research area of manufacturing system. However, some JSPs, even for moderate size instances, are very difficult to find an optimal solution within a reasonable time because of the process constraints and the complex large solution space. In this paper, an adaptive multi-population genetic algorithm (AMGA) has been proposed to solve this problem. Firstly, using multi-populations and adaptive crossover probability can enlarge search scope and improve search performance. Secondly, using adaptive mutation probability and elite replacing mechanism can accelerate convergence speed. The approach is tested for some classical benchmark JSPs taken from the literature and compared with some other approaches. The computational results show that the proposed AMGA can produce optimal or near-optimal values on almost all tested benchmark instances. Therefore, we can believe that AMGA can be considered as an effective method for solving JSP.     

基于混合智能算法的多资源约束项目优化调度

 基于关键链项目管理(critical chain project management,CCPM),利用一种混合智能优化算法求解多资源约束项目调度问题,解决传统调度优化算法的不足,提高这类问题的求解质量.首先利用一类启发式算法识别项目关键链,并设置缓冲区尺寸,以项目总工期和在制品库存为优化目标建立数学模型,设计一种混合智能优化算法求解,并对项目问题库中的j30hrs.sm问题和某生产型项目进行实验分析,得到优化的结果.实验表明,采用混合智能算法求解这类问题能得到明显优于一般调度优化算法的结果.     

An adaptive memory programming framework for the resource-constrained project scheduling problem

The Resource-Constrained Project Scheduling Problem (RCPSP) is one of the most intractable combinatorial optimisation problems that combines a set of constraints and objectives met in a vast variety of applications and industries. Its solution raises major theoretical challenges due to its complexity, yet presenting numerous practical dimensions. Adaptive memory programming (AMP) is one of the most successful frameworks for solving hard combinatorial optimisation problems (e.g. vehicle routing and scheduling). Its success stems from the use of learning mechanisms that capture favourable solution elements found in high-quality solutions. This paper challenges the efficiency of AMP for solving the RCPSP, to our knowledge, for the first time in the literature. Computational experiments on well-known benchmark RCPSP instances show that the proposed AMP consistently produces high-quality solutions in reasonable computational times.