Heuristics for multimode scheduling problems with dedicated resources

We study scheduling problems with multiple modes and dedicated resources arising in production and project management, which constitute a special class of the general multimode resource-constrained project scheduling problem. A task may require simultaneously a set of discrete, renewable resources to be processed and the processing can be performed in different modes, that is with different resource sets, processing times, or costs. Precedence constraints can exist among tasks. The total budget that can be allocated to the project can be limited. The problem consists of identifying a mode for each task and a starting time for its processing respecting precedence, resource, and budget constraints. A graph model and an iterative solution scheme are presented. Specific heuristic algorithms for the cases with and without budget constraints are given and computational results are discussed.     

Mixed-integer linear programming for resource leveling problems

We consider project scheduling problems subject to general temporal constraints, where the utilization of a set of renewable resources has to be smoothed over a prescribed planning horizon. In particular, we consider the classical resource leveling problem, where the variation in resource utilization during project execution is to be minimized, and the so-called “overload problem”, where costs are incurred if a given resource-utilization threshold is exceeded. For both problems, we present new mixed-integer linear model formulations and domain-reducing preprocessing techniques. In order to strengthen the models, lower and upper bounds for resource requirements at particular points in time, as well as effective cutting planes, are outlined. We use CPLEX 12.1 to solve medium-scale instances, as well as instances of the well-known test set devised by Kolisch et al. (1999). Instances with up to 50 activities and tight project deadlines are solved to optimality for the first time.     

Preemptive scheduling of interval orders is polynomial

In 1979, Papadimitriou and Yannakakis gave a polynomial time algorithm for the scheduling of jobs requiring unit completion times when the precedence constraints form an interval order. The authors solve here the corresponding problem, for preemptive scheduling (a job can be interrupted to work on more important tasks, and completed at a later time, subject to the usual scheduling constraints.) The m-machine preemptive scheduling problem is shown to have a polynomial algorithm, for both unit time and variable execution times as well, when the precedence constraints are given by an interval order.     

The multi-mode resource-constrained project scheduling problem with generalized precedence relations

In this paper, we tackle the challenging problem of scheduling activities to minimize the project duration, in which the activities (a) are subject to generalized precedence relations, (b) require units of multiple renewable, non-renewable and doubly constrained resources for which a limited availability is imposed, and (c) can be performed in one of several different ways, reflected in multiple activity scenarios or modes. These multiple modes give rise to several kinds of trade-offs (time/resource, time/cost and resource/resource trade-offs) which allow for a more efficient allocation and use of resources. We present a local search-based solution methodology which is able to handle many real-life project scheduling characteristics such as time-varying resource requirements and availabilities, activity ready times, due dates and deadlines, activity overlaps, activity start time constraints and other types of temporal constraints.     

Resource-constrained job scheduling with recyclable resources

In resource-constrained project scheduling problems, resources are typically classified as being either renewable, non-renewable, or doubly-constrained. A new resource classification, recyclable, is introduced. Notation and a generalized problem formulation are developed for resource-constrained job scheduling problems where resources are recyclable. This foundation is then used for studying the single-machine scheduling problem with tooling constraints. For a given set of jobs, the problem is to find the job sequence, tool type quantities, and tool recycling schedule such that the sum of job completion times and quantity of tools allocated are both minimized. Two solution approaches are developed, and examples are used to compare and contrast the approaches. The results indicate that the ‘traditional’ job scheduling approach (i.e. schedule jobs first, then tools) can lead to sub-optimal solutions. Furthermore, by scheduling jobs and tools simultaneously, it may be possible to attain a given level of performance with fewer tools.     

Scheduling three chains on two parallel machines

We consider the problem of scheduling n tasks subject to chain-precedence constraints on two identical machines with the objective of minimizing the makespan. The problem is known to be strongly NP-hard. Here, we prove that it is binary NP-hard even with three chains. Furthermore, we characterize the complexity of this case by presenting a pseudopolynomial time algorithm and a fully polynomial time approximation scheme.     

Scheduling with few changes

In this work we consider scheduling problems where a sequence of assignments from products to machines – or from tasks to operators, or from workers to resources – has to be determined, with the goal of minimizing the costs (=money, manpower, and/or time) that are incurred by the interplay between those assignments. To account for the different practical requirements (e.g. few changes between different products/tasks on the same machine/operator, few production disruptions, or few changes of the same worker between different resources), we employ different objective functions that are all based on elementary combinatorial properties of the schedule matrix. We propose simple and efficient algorithms to solve the corresponding optimization problems, and provide hardness results where such algorithms most likely do not exist.     

一类加工时间依赖资源的单机排序问题

讨论了一类有准备时间且任务的加工时间依赖资源的单机排序问题.目标函数为最大完工时间与分配给各任务资源消耗量的加权线性组合.给出了问题的若干相关性质.在此基础上,对于任务之间无优先约束和有任意优先约束的情况.分别给出了最优排列算法和最优资源分配方法.并用数值例子作了说明.     

Sufficient Global Optimality Conditions for Bivalent Quadratic Optimization

We prove a sufficient global optimality condition for the problem of minimizing a quadratic function subject to quadratic equality constraints where the variables are allowed to take values –1 and 1. We extend the condition to quadratic problems with matrix variables and orthonormality constraints, and in particular to the quadratic assignment problem.     

Review of properties of different precedence graphs for scheduling problems

Precedence constraints are a part of a definition of any scheduling problem. After recalling, in precise graph-theoretical terms, the relations between task-on-arc and task-on-node representations, we show the equivalence of two distinct results for scheduling problems. Furthermore, again using these links between representations, we exhibit several new polynomial cases for various problems of scheduling preemptable tasks on unrelated parallel machines under arbitrary resource constraints.     

Nodal aggregation of resource constraints in a shortest path problem

The shortest path problem with resource constraints consists of finding the minimum cost path between two specified points while respecting constraints on resource consumption. Its solving by a dynamic programming algorithm requires a computation time increasing with the number of resources. With the aim of producing rapidly a good heuristic solution we propose to reduce the state space by aggregating resources. Our approach consists of projecting the resources on a vector of smaller dimension and then to dynamically adjust the projection matrix to get a better approximation of the optimal solution. We propose an adjustment based on Lagrangian and surrogate relaxations in a column generation framework, in which the sub-problems are shortest path problems with resource constraints. We adjust the multipliers only one time at each column generation iteration. This permit to obtain good solutions of the scheduling problem in few time.     

Parallel machine scheduling with a convex resource consumption function

We consider some problems of scheduling jobs on identical parallel machines where job-processing times are controllable through the allocation of a nonrenewable common limited resource. The objective is to assign the jobs to the machines, to sequence the jobs on each machine and to allocate the resource so that the makespan or the sum of completion times is minimized. The optimization is done for both preemptive and nonpreemptive jobs. For the makespan problem with nonpreemptive jobs we apply the equivalent load method in order to allocate the resources, and thereby reduce the problem to a combinatorial one. The reduced problem is shown to be NP-hard. If preemptive jobs are allowed, the makespan problem is shown to be solvable in O(n²) time. Some special cases of this problem with precedence constraints are presented and the problem of minimizing the sum of completion times is shown to be solvable in O(n log n) time.     

A real-time man-in-loop threat evaluation and resource assignment in defense

Efficient weapon threat assignment reflects military proficiency and requires prompt decision while managing the available resources. An important problem which commanders/decision makers face is to optimally utilize the resources in complex and time constraints situations. Several solutions have been proposed in the literature. In this paper, an innovative approach is proposed for threat evaluation and weapon assignment (TEWA) by following 3-dimensional stable marriage algorithm (3-D SMA). This proposed model incorporates new parameters and constraints i.e. supply chain, inventory of resources and multiple threats-weapons assignments that outperforms the previous techniques. This suggested model is based on threat perception followed by an integration of parametric based automatic threat evaluation technique for further weapon scheduling and assignment problem keeping in view that the threat with greater threat index has higher priority to be intercepted and weapons’ kill probability. The experimental section shows that our proposed approach has greatly improved in comparison with other approaches. The results showed that the threat neutralization is improved up to 25% reducing the usage of ammunition till 31.1%. The damage of assets abridged to 28.5% in comparison with existing approaches. The proposed approach elucidates that TEWA is an efficient real-time threat perception and optimal multi-threat scheduling problem at weapons’ resolution. It is a three-stage process, where the first stage perceives the threat, the second stage works on threat evaluation and the final stage focuses on weapon scheduling and assignment problem. The addition of new parameters and constraints in the new proposed model makes it a unique approach in which more accurate results, in neutralizing the threats, are obtained with less use of ammunition and damage of assets that makes TEWA more effective and efficient tool for optimum decision making in time critical situations.     

A multiple-tree search procedure for the resource-constrained project scheduling problem

For over three decades, researchers have sought effective solution procedures for PERT/CPM types of scheduling problems under conditions of limited resource availability. This paper presents a procedure for this problem which takes advantage of the emerging technology provided by multiple parallel processors to find and verify an optimal schedule for a project under conditions of multiple resource constraints. In our approach, multiple solutions trees are searched simultaneously in the quest for a minimum duration schedule. Global upper and lower bound information in common memory is shared among processors, enabling one or several processors to prune potentially significant portions of its search tree based upon bounds discovered by a processor using a different search tree. Computational experience is reported both for problems in which resources are available in constant amounts per period, as well as the much more difficult problem in which the resources available are allowed to vary over the schedule horizon (e.g., travel, sick leave, assignment to other tasks or projects, and so forth). The modular multiple-tree search procedure described in this paper is quite general, permitting most types of existing serial search strategies to be adapted to this approach where multiple processors are available.     

Scheduling subject to resource constraints: classification and complexity

In deterministic sequencing and scheduling problems, jobs are to be processed on machines of limited capacity. We consider an extension of this class of problems, in which the jobs require the use of additional scarce resources during their execution. A classification scheme for resource constraints is proposed and the computational complexity of the extended problem class is investigated in terms of this classification. Models involving parallel machines, unit-time jobs and the maximum completion time criterion are studied in detail; other models are briefly discussed.     

资源受限下森林火灾应急救援多目标调度优化

许多森林火灾由于救援资源受限而不能在第一时间扑灭,导致火灾扩大蔓延,进而造成更大的森林资源损失。因此,在救援资源受限情形下,如何对消防救援车辆进行合理的调度安排以快速和低成本地扑灭火灾已成为亟待解决的现实问题。本文研究了一类资源受限下森林火灾应急救援多目标调度优化问题,为该问题构建了多目标混合整数非线性规划模型,优化目标为同时最小化总灭火救援时间和救援车辆总行驶距离。为有效求解该问题,首先将上述非线性模型等价转化为线性模型。然后提出ε-约束法和模糊逻辑相结合的算法对问题进行求解。最后,以大兴安岭山发生的火灾案例和随机生成仿真算例对模型和算法有效性进行验证,结果表明所提出的模型和算法能够有效解决资源受限下森林火灾应急救援问题,并为决策者提供最优的消防调度方案。     

Multiple-Project Scheduling with Controllable Project Duration and Hard Resource Constraint: Some Solvable Cases

In many large-scale project scheduling problems, multiple projects are either taking place at the same time or scheduled into a tight sequence in order to efficiently share a common resource. One example of this is the computing resource allocation at an Application Service Provider (ASP) which provides data processing services for multiple paying customers. Typical services provided by ASPs are data mining, payroll processing, internet-based storage backup services and Customer Relation Management (CRM) services. The processing mode of an ASP can be either batch or concurrent, depending on the type service rendered. For example, for CPU intensive or long processing time required services, it would be more economical to processes one customer request at a time in order to minimize the context switching overhead. While the data transaction processes within a service request are subject to certain precedence relationships, the requests from different customers to an ASP are independent of each other, and the total time required to process a service request depends on the computing resource allocated to that request. The related issue of achieving an optimal use of resources at ASPs leads to problem of project scheduling with controllable project duration.In this paper, we present efficient algorithms for solving several special cases of such multi-project scheduling problems with controllable project duration and hard resource constraints. Two types of problems are considered. In type I, the duration of each project includes a constant and a term that is inversely proportional to the amount of resource allocated. In type II, the duration of each individual project is a continuous decreasing function of the amount of resource allocated.     

A heuristic solution framework for the resource constrained (multi-)project scheduling problem with sequence-dependent transfer times

We consider the problem of scheduling multiple projects subject to joint resource constraints. Most approaches proposed in the literature so far are based on the unrealistic assumption that resources can be transferred from one project to the other without any expense in time or cost. In order to contribute to closing this gap to reality, we generalise the multi-project scheduling problem by additionally including sequence- and resource-dependent transfer times, which represent setup activities necessary when a resource is removed from one project and reassigned to another (or from one job to another within the same project). In this paper, we define the modified resource constrained multi-project scheduling problem with transfer times (called RCMPSPTT), which aims at minimising the multi-project duration for the single-project approach or the mean project duration for the multi-project approach. We formulate both perspectives as an integer linear program, propose priority rule based solution procedures and present results of comprehensive computational experiments. Provided that the combination of scheduling scheme and priority rules is chosen appropriately, the procedures obtain good results. In particular, resource oriented priority rules are identified to be successful.     

Open shop scheduling with some additional constraints

An open shop scheduling problem is presented; preemptions during processing of a job on a processorp is allowed but the job cannot be sent on another processorq before it is finished onp. A graph-theoretical model is described and a characterization is given for problems where schedules with such restricted preemptions useT time units whereT is the maximum of the processing times of the jobs and of the working times of the processors. The general case is shown to be NP-complete. We also consider the case where some constraints of simultaneity are present. Complexity of the problem is discussed and a solvable case is described.