Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting

This paper presents results from an extensive computational study of the multi-mode resource-constrained project scheduling problem when activities can be split during scheduling under situations where resources may be temporarily not available. All resources considered are renewable and each resource unit may not be available at all times due to resource vacations, which are known in advance, and assignment to other finite duration activities. A designed experiment is conducted that investigates project makespan improvement when activity splitting is permitted in various project scenarios, where different project scenarios are defined by parameters that have been used in the research literature. A branch-and-bound procedure is applied to solve a number of small project scheduling problems with and without activity splitting. The results show that, in the presence of resource vacations and temporary resource unavailability, activity splitting can significantly improve the optimal project makespan in many scenarios, and that the makespan improvement is primarily dependent on those parameters that impact resource utilization.     

An Overview of Scheduling Problems Arising in Satellite Communications

Satellite communications, like batches of work in a job shop, need to be scheduled in order to use their resources as efficiently as possible. The most common satellite communications system in use today is known as Time Division Multiple Access (TDMA), in which data from earth stations is buffered before being transmitted to the appropriate receiver on a satellite. Cycles of transmission are fixed for all stations. Since the same satellite will be used for routeing data in several different ways, a schedule must be devised to use the receivers, repeaters and transmitters on board to minimize the time needed for completion of a batch of work. This paper is a survey of current scheduling algorithms used for optimizing satellite communications resources. Apart from telecommunications, the methods presented here could be applied to more general scheduling problems with renewable resources but without precedence 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.     

A Petri Net based algorithm for minimizing total tardiness in flexible manufacturing systems

Petri Nets have been extensively used for modeling and simulating of the dynamics of flexible manufacturing systems. Petri Nets can capture features such as parallel machines, alternative routings, batch sizes, multiplicity of resources, to name but a few. However, Petri Nets have not been very popular for scheduling in manufacturing due to the Petri Net “state explosion” combined with the NP-hard nature of many of such problems. A promising approach for scheduling consists of generating only portions of the Petri Net state space with heuristic search methods. Thus far, most of this scheduling work with Petri Nets has been oriented to minimize makespan. The problem of minimizing total tardiness and other due date-related criteria has received little attention. In this paper, we extend the Beam A^* Search algorithm presented in a previous work with capability to handle the total tardiness criterion. Computational tests were conducted on Petri Net models of both flexible job shop and flexible manufacturing systems. The results suggest that the Petri Net approach is also valid to minimize due date related criteria in flexible systems.     

新中考中的排课问题

为提高初中学业水平和综合素质教育,近几年有些地方中考进行改革,要求学生进行学科选择。新中考课程分为选修和必修两大类。必修课程为语文、数学、英语,选修课程为其他六门课程,从中选出三项。把最后总成绩作为中考录取的标准。跟传统排课不同,这里排课要求每人一张课表,问题变得复杂困难。本文以北京某初三课程为例,研究了新中考的排课问题。一般情况下约束和变量是上百万级的,无法求解。本文利用整数规划建模,然后把该问题转化成多阶段问题,每个阶段给出小问题的解,这样使得问题的求解变得可行。最终的排课结果,仅比预期增加三位老师就可以实现新中考的排课问题。本文的求解过程给新中考排课带来了新的启发。     

Solving the discrete-continuous project scheduling problem via its discretization

In this paper a discrete-continuous project scheduling problem is considered. In this problem activities simultaneously require discrete and continuous resources. The processing rate of each activity depends on the amount of the continuous resource allotted to this activity at a time. All the resources are renewable ones. The activities are nonpreemtable and the objective is to minimize the makespan. Discretization of this problem leading to a classical (i.e. discrete) project scheduling problem in the multi-mode version is presented. A simulated annealing (SA) approach to solving this problem is described and tested computationally in two versions: with and without finding an optimal continuous resource allocation for the final schedule. In the former case a nonlinear solver is used for solving a corresponding convex programming problem. The results are compared with the results obtained using SA for the discrete-continuous project scheduling problem where the nonlinear solver is used for exact solving the continuous part in each iteration. The results of a computational experiment are analyzed and some conclusions are included.     

An empirical comparison of heuristic methods for creating maximally diverse groups

This research identifies, describes, and empirically contrasts five heuristics for forming maximally diverse groups of any specified size from a given population. Diversity is based upon multiple criteria specified by the decision maker. The problem has immediate application in academic or training settings where it may be desired to create class sections, or project groups within classes, such that students are immersed in a diverse environment. Furthermore this research has an even broader utility, as the problem is mathematically identical to an eclectic set of applications ranging from final exam scheduling to VLSI design. Here we consider five different heuristics, drawn from student-workgroup assignment and final exam scheduling applications. The methods are tested on a ‘real-world’ data set and evaluated on the criteria of solution quality and computational resources.     

Tracking Demands in Optimal Control of Managerial Systems with Continuously-Divisible, Doubly Constrained Resources

The paper addresses problems of allocating continuously divisible resources among multiple production activities. The resources are allowed to be doubly constrained, so that both usage at every point of time and cumulative consumption over a planning horizon are limited as it is often the case in project and production scheduling. The objective is to track changing in time demands for the activities as closely as possible. We propose a general continuous-time model that states the problem in a form of the optimal control problem with non-linear speed-resource usage functions. With the aid of the maximum principle, properties of the solutions are derived to characterize optimal resource usage policies. On the basis of this analytical investigation, numerical scheduling methods are suggested and computationally studied. This revised version was published online in July 2006 with corrections to the Cover Date.     

A truck scheduling problem arising in intermodal container transportation

We address a truck scheduling problem that arises in intermodal container transportation, where containers need to be transported between customers (shippers or receivers) and container terminals (rail or maritime) and vice versa. The transportation requests are handled by a trucking company which operates several depots and a fleet of homogeneous trucks that must be routed and scheduled to minimize the total truck operating time under hard time window constraints imposed by the customers and terminals. Empty containers are considered as transportation resources and are provided by the trucking company for freight transportation. The truck scheduling problem at hand is formulated as Full-Truckload Pickup and Delivery Problem with Time Windows (FTPDPTW) and is solved by a 2-stage heuristic solution approach. This solution method was specially designed for the truck scheduling problem but can be applied to other problems as well. We assess the quality of our solution approach on several computational experiments.     

Integrated production and material handling scheduling using mathematical programming and constraint programming

In this article, we propose an integrated formulation of the combined production and material handling scheduling problems. Traditionally, scheduling problems consider the production machines as the only constraining resource. This is however no longer true as material handling vehicles are becoming more and more valuable resources requiring important investments. Their operations should be optimized and above all synchronized with machine operations. In the problem addressed in this paper, a job shop context is considered. Machines and vehicles are both considered as constraining resources. The integrated scheduling problem is formulated as a mathematical programming model and as a constraint programming model which are compared for optimally solving a series of test problems. A commercial software (ILOG OPLStudio) was used for modeling and testing both models.     

A new bounding mechanism for the CNC machine scheduling problems with controllable processing times

In this study, we determine the upper and lower bounds for the processing time of each job under controllable machining conditions. The proposed bounding scheme is used to find a set of discrete efficient points on the efficient frontier for a bi-criteria scheduling problem on a single CNC machine. We have two objectives; minimizing the manufacturing cost (comprised of machining and tooling costs) and minimizing makespan. The technological restrictions of the CNC machine along with the job specific parameters affect the machining conditions; such as cutting speed and feed rate, which in turn specify the processing times and tool lives. Since it is well known that scheduling problems are extremely sensitive to processing time data, system resources can be utilized much more efficiently by selecting processing times appropriately.     

Joint production and preventive maintenance scheduling for a single degraded machine by considering machine failures

Production scheduling and maintenance planning are two interdependent issues that most often have been investigated independently. Although both preventive maintenance (PM) and minimal repair affect availability and failure rate of a machine, only a few researchers have considered this interdependency in the literature. Furthermore, most of the existing joint production and preventive maintenance scheduling methods assume that machine is available during the planning horizon and consider only a possible level for PM. In this research, an integrated model is proposed that coordinates preventive maintenance planning with single-machine scheduling to minimize the weighted completion time of jobs and maintenance cost, simultaneously. This paper not only considers multiple PM levels with different costs, times and reductions in the hazard rate of the machine, but also assumes that a machine failure may occur at any time. To illustrate the effectiveness of the suggested method, it is compared to two situations of no PM and a single PM level. Eventually, to tackle the suggested problem, multi-objective particle swarm optimization and non-dominated sorting genetic algorithm (NSGA-II) are employed and their parameters are tuned Furthermore, their performances are compared in terms of three metrics criteria.     

Preemptive scheduling of independent jobs on parallel machines subject to financial constraints

The paper deals with the preemptive scheduling of independent jobs on parallel unrelated machines with the use of additional renewable resources (manpower, facilities) and the consumption of a nonrenewable resource (money). Money becomes available at different dates in specified amounts (financial constraints). Two scheduling criteria are considered: schedule length and total cost. The algorithm consists in solving a parametric linear program and using its results to construct a most satisfactory schedule in polynomial time. The reduction of job preemptions in a feasible schedule is considered.     

Solving project scheduling problem with the philosophy of fuzzy random programming

Project scheduling problem is to determine the schedule of allocating resources to achieve the trade-off between the project cost and the completion time. In real projects, the trade-off between the project cost and the completion time, and the uncertainty of the environment are both considerable aspects for managers. Due to the complex external environment, this paper considers project scheduling problem with coexisted uncertainty of randomness and fuzziness, in which the philosophy of fuzzy random programming is introduced. Based on different ranking criteria of fuzzy random variables, three types of fuzzy random models are built. Besides, a searching approach by integrating fuzzy random simulations and genetic algorithm is designed for searching the optimal schedules. The goal of the paper is to provide a new method for solving project scheduling problem in hybrid uncertain environments.     

Sequential clinical scheduling with service criteria

This study investigates sequential appointment scheduling with service criteria. It uses a constraint-based approach with service criteria bounded in a constraint set in contrast to the more typical weighted linear objective function. Properties are derived and a sequential scheduling algorithm is developed. Fairness properties of generated schedules are considered in detail, where fairness is the uniformity of performance across patients. New unfairness measures are proposed and used to capture the inequity among patients assigned to different slots. Other criteria such as expectation and variance of patient waiting time, queue length, and overtime are also considered. The fairness/revenue tradeoff is investigated as is the flexibility of the constraint-based approach in handling unavailable time periods.     

A framework for an interactive project scheduling system under limited resources

In this paper, we propose a framework for an interactive project scheduling system under limited resources. The framework includes a modelling module (model) and a scheduling module (scheduler). The modelling module model allows the Decision Maker (DM) to develop his/her own model with features such as alternative operating modes for activities; renewable, nonrenewable and/or doubly-constrained resource constraints; general cash flow patterns, related to the realization of activities or events; and progress payments distributed over the project span. The performance criteria include the maximization of Net Present Value (NPV), and either the minimization of maximum tardiness (when a project due date exists) or the minimization of the project duration (when there is no project due date). The scheduler is developed on a constraint-based scheduling algorithm, which is called Local Constraint Based Analysis (lcba) and which has previously been tested and shown to produce near-optimal results with respect to the criterion of minimizing project duration. The decisions taken in the scheduler consist of determining the start times of activities and the specific operating modes in which they are to be realized. The decisions are taken by activating relevant essential conditions in lcba and in cases where resource conflicts are not resolved, the DM reaches a final decision by testing the alternatives proposed by lcba through a what-if routine. The scheduler represents a realistic scheduling system which is useful not only in the planning phase of a project but can also be employed during the progress of a project for updating the project plan, if necessary. An important feature is that the project plan can be updated by performing the least modification of future commitments. It is possible to freeze the activities already scheduled in the near future while admitting the changes in the activity/network information.     

On Providing Quality of Service in Grid Computing through Multi-objective Swarm-Based Knowledge Acquisition in Fuzzy Schedulers

Nowadays, Grid computing is increasingly showing a service-oriented tendency and as a result, providing quality of service (QoS) has raised as a relevant issue in such highly dynamic and non-dedicated systems. In this sense, the role of scheduling strategies is critical and new proposals able to deal with the inherent uncertainty of the grid state are needed in a way that QoS can be offered. Fuzzy rule-based schedulers are emerging scheduling schemas in Grid computing based on the efficient management of grid resources imprecise state and expert knowledge application to achieve an efficient workload distribution. Given the diverse and usually conflicting nature of the scheduling optimization objectives in grids considering both users and administrators requirements, these strategies can benefit from multi-objective strategies in their knowledge acquisition process greatly. This work suggests the QoS provision in the grid scheduling level with fuzzy rule-based schedulers through multi-objective knowledge acquisition considering multiple optimization criteria. With this aim, a novel learning strategy for the evolution of fuzzy rules based on swarm intelligence, Knowledge Acquisition with a Swarm Intelligence Approach (KASIA) is adapted to the multi-objective evolution of an expert grid meta-scheduler founded on Pareto general optimization theory and its performance with respect to a well-known genetic strategy is analyzed. In addition, the fuzzy scheduler with multi-objective learning results are compared to those of classical scheduling strategies in Grid computing.     

Tabu search for a class of scheduling problems

Scheduling problems are often modeled as resourceconstrained problems in which critical resource assignments to tasks are known and the best assignment of resource time must be made subject to these constraints. Generalization toresource scheduling, where resource assignments are chosen concurrently with times results is a problem which is much more difficult. A simplified model of the general resource scheduling model is possible, however, in which tasks must be assigned a singleprimary resource, subject to constraints resulting from preassignment ofsecondary, or auxiliary, resources. This paper describes extensions and enhancements of tabu search for the special case of the resource scheduling problem described above. The class of problems is further restricted to those where it is reasonable to enumerate both feasible time and primary resource assignments. Potential applications include shift oriented production and manpower scheduling problems as well as course scheduling where classrooms (instructors) are primary and instructors (rooms) and students are secondary resources. The underlying model is a type of quadratic multiple choice problem which we call multiple choice quadratic vertex packing (MCQVP). Results for strategic oscillation and biased candidate sampling strategies are shown for reasonably sized real and randomly generated, synthetic, problem instances. The strategies are compared with other variations using consistent measures of solution time and quality developed for this study.     

Scheduling non-critical activities using multicriteria approach

In many projects the problem of selecting the start time of a non-critical activity arises. Usually it is possible to use the “as soon as possible” or “as late as possible” rules. In some situations, however, the result of such a decision depends on external factors such as exchange rate. This leads to an approach in which the problem of scheduling non-critical activities is solved using an expanded Cox–Ross–Rubinstein (CRR) binomial tree method. In the paper a bi-criteria problem of determining the start time of a non-critical activity is considered. We assume that the early start and the late start of the activity have been identified using Critical Path Method, but the project manager is free to select the time when the activity will actually be started. This decision cannot, however, be changed later, as it is associated with the allocation of key resources. Two main criteria are considered: cost and risk. While cost depends on exchange rate, risk increases with the delay of the start of the activity. The problem can be described as a dynamic process. We propose a new interactive technique for solving such a bi-criteria decision making problem under risk. The procedure uses trade-offs to identify a candidate solution. The CRR binomial method is applied to evaluate the cost of the activity.

     

基于约束满足问题的中继卫星调度问题研究

中继卫星任务规划与调度是中继卫星系统应用中的重要问题。根据航天器的空间轨道参数，得到中继卫星与用户航天器之间的可见时间窗口。在此基础上，通过分析中继卫星系统中各种资源之间的约束关系、任务优先级与调度准则，建立中继卫星系统的任务调度模型。仿真结果表明，基于约束规划理论建立中继卫星调度模型是解决中继卫星调度问题的有效方法。