In many scheduling applications it is required that the processing of some job be postponed until some other job, which can be chosen from a pregiven set of alternatives, has been completed. The traditional concept of...
详细信息
In many scheduling applications it is required that the processing of some job be postponed until some other job, which can be chosen from a pregiven set of alternatives, has been completed. The traditional concept of precedenceconstraints fails to model such restrictions. Therefore, the concept has been generalized to so-called and/or precedence constraints which can cope with this kind of requirement. In the context of traditional precedenceconstraints, feasibility, transitivity, and the computation of earliest start times for jobs are fundamental, well-studied problems. The purpose of this paper is to provide efficient algorithms for these tasks for the more general model of and/or precedence constraints. We show that feasibility as well as many questions related to transitivity can be solved by applying essentially the same linear-time algorithm. In order to compute earliest start times we propose two polynomial-time algorithms to cope with different classes of time distances between jobs.
In this research, a new variant of the vehicle routing problem with time windows is studied where a given number of dispersed customers are related to each other through and/or precedence constraints. This generalizat...
详细信息
In this research, a new variant of the vehicle routing problem with time windows is studied where a given number of dispersed customers are related to each other through and/or precedence constraints. This generalization is necessary for problems like order picker routing models in which the target locations cannot be reached in any sequences, but AND/OR relations need to be taken into account in retrieving requested items. In such an application, a node cannot be visited before its AND-type predecessors, while at least one of its OR-type predecessors needs to be reached before that. We propose a Mixed Integer Linear Programming (MILP) model to formulate the problem. In addition, a meta-heuristic algorithm based on the hybridization of Iterated Local Search and Simulated Annealing approach is developed, which lead to reasonable results in terms of CPU time and solutions accuracy for a set of instances extended from the well-known Solomon benchmark. A different perturbation procedure and several simple and fast neighborhoods are applied to make a good balance between the diversification and intensification of the search. To improve the hybrid algorithm's performance, Taguchi's method (Peace, 1993) is used to tune the algorithm parameters. A comprehensive computational analysis is conducted to assess the performance of the developed algorithm.
In the context of stochastic resource-constrained project scheduling we introduce a novel class of scheduling policies, the linear preselective policies. They combine the benefits of preselective policies and priority...
详细信息
In the context of stochastic resource-constrained project scheduling we introduce a novel class of scheduling policies, the linear preselective policies. They combine the benefits of preselective policies and priority policies;two classes that are well known from both deterministic and stochastic scheduling. We study several properties of this new class of policies which indicate its usefulness for computational purposes. Based on a new representation of preselective policies as and/or precedence constraints we derive efficient algorithms for computing earliest job start times and state a necessary and sufficient dominance criterion for preselective policies. A computational experiment based on 480 instances empirically validates the theoretical findings.
Directed Acyclic Graphs DAGs are used to represent AND/OR precedence constraint systems where AND tasks are ready to execute when all of their direct predecessors are completed and OR tasks are ready to execute when o...
详细信息
ISBN:
(纸本)0780383524
Directed Acyclic Graphs DAGs are used to represent AND/OR precedence constraint systems where AND tasks are ready to execute when all of their direct predecessors are completed and OR tasks are ready to execute when one or more but not necessarily all of their direct predecessors are completed. A proposed Imprecise Computation Technique ICT is introduced to maximize the solution quality within the available time. To examine and evaluate ICT, a Random Graph Generator algorithm RGG is created to provide a wide range of random DAGs to be used in the simulation experiments.
In a real-time system, tasks must produce logically correct results by their deadlines. These tasks usually don't need to be executed in a sequential order. Rather, certain precedenceconstraints must be handled b...
详细信息
In a real-time system, tasks must produce logically correct results by their deadlines. These tasks usually don't need to be executed in a sequential order. Rather, certain precedenceconstraints must be handled between them along with timing constraints to provide correct scheduling and consequently correct execution. In traditional precedence-constrained scheduling, a task is ready to execute when all of its direct predecessors are completed. Such task is called an AND task. In many applications, some tasks are ready to execute when one or more but not necessarily all of their direct predecessors are completed. These tasks are called OR tasks. The resultant system containing both AND and OR tasks is said to have and/or precedence constraints. Directed Acyclic Graphs DAGs are used to represent these systems. This paper introduces a method to combine both precedenceconstraints and timing constraints into the same scheduling problem. Timing constraints here are in the form of a global End-to-End Deadline EED between a start task and an end task of the AND/OR graph representing the task system. A proposed Imprecise Computation Technique ICT is introduced to maximize the solution quality within the available time. ICT is motivated by the fact that one can trade off precision with timeliness;it prevents the total processing time of the system from stretching over the EED. To examine and evaluate this proposed imprecise scheduling solution, a Random Graph Generator algorithm RGG is created to provide a wide range of random DAGs to be used in the simulation experiments.
暂无评论