Overload Checking and Edge-Finding for Robust Cumulative Scheduling

Overload Checking and Edge-Finding for Robust Cumulative Scheduling

Scheduling is an occasionally used concept to which we are accustomed in our daily life, notwithstanding keeping a standard definition for that is often overlooked. Normally, we desire to plan the activities that we are engaged in beforehand for purposes such as time saving, reducing cost charges, etc. For instance, suppose you are invited to attend the graduation ceremony of a group of students in the school, which is scheduled to start at a specified date. The place where the party takes place is located in downtown and you have to arrange for your departure in accordance with the public transportation schedule so that you arrive to the party on time. Such an occasion simply demonstrates a scheduling problem for which you need to care for two schedules, the ceremony as well as the public transportation, and these schedules are planned in advance. Since the late 1950’s and early 1960’s scheduling problems have attracted a large amount of research [7, 93]. Covered by a wide variety of disciplines such as computer science (CS), artificial Intelligence (AI), operational research (OR), engineering, manufacturing, management, maintenance, etc., scheduling problems are mostly known as an interdisciplinary field of study, as they arise in numerous application settings in the real-world. The general class of scheduling problems that we consider in this dissertation involves a group of activities to be carried out over a set of resources. The activities require certain amounts of resources to process. The activities and resources can have different interpretations, depending on the context. Moreover, most of the scheduling problems are optimization problems. That is, there is a desired objective to be attained, such as minimizing the duration of the schedule, minimizing the costs, maximizing the profits, etc. Frequently, there are given precedences among the activities, prescribing the order in which they must be processed. The basic form of a schedule usually establishes the dates at which the activities should start such that the precedence and the alternative constraints hold and the objective function is optimized. Providing such dates to acquire a valid schedule for the activities is equivalent to finding a solution for the problem. This framework for the scheduling problems is expressive enough to capture dozens of features which arise in practice. The input size of the general scheduling problems is typically proportional to the number of activities, the number of resources and the number of bits to represent the largest integer among the components of an activity. Unfortunately, the problem of solving most of the scheduling problems is NP-hard [29]. In fact, not only solving, but also verifying whether a feasible solution exists can take exponential effort. That is why relatively less attempts have been made to achieve polynomial time algorithms for the scheduling problems, thus far. In the literature, there are a variety of areas of general methods used to solve scheduling problems such as MIP (mixed integer programming), satisfiability testing (SAT), logic-based Benders decomposition (LBBD) [36, 38] and constraint programming (CP). We focus on the latter method. Constraint programming is a generic purpose paradigm to solve combinatorial problems by interpreting them in terms of constraints. A typical constraint satisfaction problem (CSP) consists of a set of decision variables, to each member of which a domain is associated. The domain includes the valid values that are assignable to the variables. Furthermore, a set of constraints that circumscribe the decision variables are established and a single objective function is to be optimized. Many problems can be presented in terms of constraints. Furthermore, many disciplines such as OR and AI, have developed methods for satisfying constraints. In particular, constraint-based scheduling provides powerful search strategies to solve scheduling problems, by taking advantage of constraint programming. Among the successful application areas of constraint programming are the cumulative and disjunctive scheduling. Cumulative scheduling differs from disjunctive scheduling in the sense that in cumulative scheduling several activities are allowed to run simultaneously. Each activity consumes a certain amount of resource, and the CUMULATIVE constraint ensures that the accumulation of resource usage by the activities underway at any time does not overflow the resource. In the disjunctive scheduling no more than one activity can execute on a resource and the DISJUNCTIVE constraint ensures that the activities do not overlap at any time. The main goal of this dissertation is to address special structures of the scheduling problems encountered in the industry, from a constraint-based viewpoint. Furthermore, we aim at tackling distinct properties of industrial scheduling problems with different objective functions that can be encountered in practical applications. Constraints can be used to encode all sort of these problems. The domains of variables in a CSP include values which are not consistent with some constraints of the problem. Removing all inconsistencies from the domain of variables with respect to the CUMULATIVE constraint is NP-Hard. However, several rules are proposed which can partially remove inconsistencies in polynomial time. The scheduling problems that we consider to a great extent rely on a problem solving paradigm from constraint programming which is called constraint propagation. This method is a reduction technique which detects inconsistencies through the repetitive analysis of the variables and makes the problem simpler to solve. The constraint propagation process uses several filtering algorithms. These algorithms discover time zones in which the activities cannot start. Discovering such time zones prevent the solver from exploring some portions of the search space where no feasible solutions lie. Since constraint programming is based upon filtering algorithms, devising efficient algorithms is essential and this objective has captured the interest of many researchers in the CP community. This dissertation makes contributions to this research area by developing efficient, effective and fast filtering algorithms to solve conventional scheduling problems.

Scheduling environments are not always static in the real world and uncertainty is prevalent in this context. For instance, the operations might take longer than expected to execute, a supply chain for resources can break down and the resources becomes unavailable, etc. Such disruptions unavoidably cause delays in the activities. On the other hand, practically, it is not possible to re-compute the solutions in such cases. Therefore, it is of crucial importance to develop filtering algorithms which deal with such environments. An approach is to maintain a robust schedule that absorbs some level of unforeseen events when at most a certain number of activities are delayed. Even though this is not mentioned as an objective function, robustness is a desired criterion in a schedule .

Although the scheduling problems are NP-complete in the general form, specializations to the properties of the problem can yield to problems that can be solved in polynomial time. For instance, if all the activities execute with the same duration over multiple resources, it is possible to find a solution. Furthermore a common objective function is to minimize the makespan, i.e. when the last task finishes. However, in practice, alternative objective functions often occur depending on the circumstances and context and yet it is essential that managers operate their business with the utmost efficiency. This dissertation particularly aims at solving more efficiently scheduling problems whose optimization criteria is not necessarily the makespan. For instance, we consider the cases such as when the amount of available resources fluctuates over time with respect to the activities. We also elaborate on specific objective functions that give rise to polynomiality .

Constraint satisfaction and constraint programming

Combinatorial optimization

Combinatorial optimization is a branch of study in applied mathematics as well as computer science whose focus is primarily to solve optimization problems. Ordinarily, the goal of a combinatorial optimization problem is to find a feasible solution over a finite and discrete structure subject to an objective function to be optimized. The following simply exemplifies a combinatorial optimization problem .

Constraint satisfaction problems

Constraint satisfaction problems (CSP) have emerged as a major area of focus for AI community researchers over the past decades. The historical roots of constraint programming (CP) can be traced back to 1960s and 1970s, where the paradigm first arose in artificial intelligence and computer graphics [81]. After it was gradually realized that a host of complex and practical problems in applied sciences could be interpreted in terms of satisfaction problems, CSP evolved into a rather mature field. Covering a large spectrum of real-world applications, such as artificial intelligence, database systems, programming languages, graphical interfaces, natural language processing and operations research, nowadays constraint programming provides a versatile tool and powerful technique to solve combinatorial optimization problems. Notably, one can recast a variety of paradigms arising in AI, including scheduling, timetabling, resource allocation, planning, assignment problems and maximum flows in terms of a CSP [69, 23].

What is a CSP?

Let us formally go over the details of CSP. A variable is a symbol to which different values could be assigned. The set of candidate values to be assigned to a variable determines the domain of the variable. In this dissertation, we are only concerned with constraint satisfaction problems with finite domains. A constraint can be regarded as a restriction established on the variable assignments. Formally, a constraint C is a logical relation defined on a set of variables. Roughly speaking, a constraint satisfaction problem (CSP) is a mathematical problem defined on a set of variables, each one with a finite and discrete domain subject to certain constraints. Definition 1.2.1. An instance of a CSP is composed of the sets X = {X1, …, Xn}, D = {dom(X1), …, dom(Xn)}, C = {C1, …, Cm}, X0 = {XC1 , …, XCm} where each Xi ∈ X, 1 ≤ i ≤ n, is a variable with the finite domain dom(Xi) ∈ D and each Cj ∈ C, 1 ≤ j ≤ m, is a constraint defined over the set XCj ∈ X0 such that XCj ⊆ X. That is, the variables in XCj are chosen from the universal set of variables X. XCj is called the scope of Cj and the cardinality of XCj , denoted |XCj |, is called the arity of Cj . A global constraint is a constraint that correlates a non-fixed number of variables with each other. Global constraints are a more general form of a constraint, that can be expressed with simpler constraints of fixed arity. Although they may be expressed as a conjunction of further constraints, they frequently simplify the model of a problem and facilitate the work of solvers by providing a concise and expressive manner of modelling a condition. The advantage of global constraints is that they provide a specialized filtering algorithm that prunes the domains of the variables much more than the conjunction of elementary constraints. As an example, the ALL-DIFFERENT(X1, …, Xn) is a global constraint which associates pairwise distinct values to the variables X1, …, Xn. It turns out that the ALL DIFFERENT constraint filters more than O(n 2 ) constraints of pairwise inequalities Xi 6= Xj for 1 ≤ i, j ≤ n [66]. The number of variables in the scope of a global constraint can take any value. That is, the arity of a global constraint is a parameter of that constraint.

Constraint programming

CSPs are intractable and belong to the class of NP-complete problems [80]. Accordingly, much efforts are made to diminish the elapsed time required to solve CSPs. Constraint programming is a technique which provides such a prospect. Constraint programming languages offer built-in constraints which make it easy to model a problem into a CSP. Thus far, there are multiple toolkits and packages designed for developing constraint-based systems, such as CHIP [22], Choco [60], Gecode [31], Comet [35], etc. Our experiments presented in this dissertation were implemented via Choco solver, which is an open source CP library in Java.

Scheduling Theory

Project scheduling problems deal with the temporal allocation of a variety of activities to a set of resources over time in order to achieve some objectives. Since this concept can be interpreted quite broadly, a multitude of practical problems arising in diverse areas such as transportation, distribution settings, manufacturing environments, etc. fit within this framework. Notably, the scheduling problems are challenging combinatorial optimization problems. Since the early days of operations research, scheduling problems have been intensively investigated by the OR and AI community [7, 93, 70, 77]. This scenario can be considered from different mathematical points of view. In this dissertation, we take it into consideration from a constraint-based standpoint.

Scheduling framework

In order to have a proper statement of the scheduling problems which are most frequently used throughout the forthcoming chapters, this section describes the basic terminology, notations and different types of the scheduling problems.

Terminology and representation

A traditional scheduling problem is formulated by a triple (R, I, γ), where m ≥ 1 shared resources (or machines) R = {R1, …, Rm} are required to process a set of n tasks (or activities) I = {1, …, n} such that a desired objective function γ is attained. In the context of this dissertation, each Rj ∈ R, 1 ≤ j ≤ m, is capable of performing each task i ∈ I, equally and all the resources are identical. If a task i has access to all resources of R whatsoever, the resources are called parallel. The resources and tasks in the problem vary depending on their associated organization. Presuming the time is discrete, that is the values of the attributes are integers, we establish the following conventions in order to characterize each task i ∈ I. The release time or the earliest starting time of i, denoted esti , is the earliest date at which i becomes available to be executed on any resource. The deadline or the latest completion time of i, denoted lcti , is the latest date at which i can cease to execute on any resource. The duration or processing time of i, denoted pi , is the total elapsed time if i executes on any resource. The latest starting time (lsti) of a task is the maximum date at which it can start executing and the earliest completion time (ecti) of a task is the minimum date at which it can cease to execute. These two values are computed with lsti = lcti −pi and ecti = esti +pi , respectively. The missing date of i, denoted oi , is the earliest time point by starting at which i oversteps its deadline. This component is computed by oi = lsti +1.

A family of scheduling problems

The family of shop scheduling problems is composed of job shop, open shop and flow shop problems. In these problems, I is clustered into sets of jobs. As a common property for these problems, the jobs belonging to I ought to execute on the resources of R and each resource can run at most one job at the same time. In the job shop problem the jobs of each task have their own order of execution on the resources. In the flow shop problem, the order of execution of jobs within the tasks are identical for each task. In the open shop problem the order of execution of jobs on the resources is immaterial. Ordinarily, in the shop scheduling problems the objective is to minimize the makespan.

Classifying scheduling in terms of resource and task types

One can categorize the major scheduling problems by the resource configuration. A scheduling problem for which each resource can execute at most one task at each time is said to be disjunctive. In the disjunctive scheduling, ci = C for i ∈ I. The family of shop scheduling problems fall into this category. The scheduling problems in which several tasks can run on a resource, provided the capacity of the resource does not exceed is said to be cumulative. Depending on the type of tasks found in the problem, we distinguish non-preemptive scheduling and preemptive scheduling. In non-preemptive scheduling, the tasks are not allowed to be interrupted. That is, each task must execute without interruption ever since it starts executing until it finishes. In preemptive scheduling, the tasks can be interrupted during their execution and resumed possibly on another resource. Notice that in non-preemptive scheduling, the constraint Si + pi = Ei holds and in preemptive scheduling, the constraint Si + pi ≤ Ei holds.

Conclusion

Scheduling is a decision-making process that is concerned with the assignment of execution times to the activities. This work dealt with deterministic scheduling problems in the presence of scarce resources which must be allocated to the activities over time. The limitation on the availability of resources in this context as well as the presence of technological precedence constraints causes conflicts between concurrent scheduling of the activities over resources which makes the paradigm complex and challenging. Although branch and bound or integer programming methodologies can give rise to optimal solutions for problems whose data are relatively small, the increasing size of the problem yields quite a complex problem which requires exponential effort to solve. Therefore, it is essential to investigate more efficient methods to solve scheduling problems in large scales. The generic form of the scheduling problems considered in this thesis is represented as an instance of a constraint satisfaction problem (CSP) in which there is a set of variables, each of which associated to a set of possible values (domains), and a set of constraints interrelating the variables. An assignment of values to the variable, so that all the constraints are satisfied leads to a solution for CSP. The major objective of this work was to investigate the application of constraint programming for industrial scheduling problems. The need in practical applications in the industry is to take into consideration distinct properties of the industrial scheduling problems. The focus of this thesis was to fulfill this need by viewing the constraint-based scheduling problems from different standpoints. Since CSPs are NP-hard to solve in general, so are the scheduling problems. Nonetheless, there are specializations to the scheduling problem that can be solved in polynomial time. We aimed at developing effective solutions and designing filtering algorithms to find optimal schedules or to shrink the search space for scheduling problems in a variety of contexts.

Table des matières

Introduction 
1 Constraint satisfaction and constraint programming
1.1 Combinatorial optimization
1.2 Constraint satisfaction problems
1.2.1 What is a CSP?
1.3 Constraint programming
1.3.1 Searching solutions
1.3.2 Supports and local consistency
1.3.3 Filtering algorithms and constraint propagation
2 Scheduling Theory
2.1 Scheduling framework
2.1.1 Terminology and representation
2.1.2 Objective Functions
2.1.3 A family of scheduling problems
2.1.4 Classifying scheduling in terms of resource and task types
2.1.5 Three-field characterization
2.2 Global Constraints Used in Scheduling
2.2.1 ALL-DIFFERENT constraint
2.2.2 Global Cardinality
2.2.3 INTER-DISTANCE
2.2.4 MULTI-INTER-DISTANCE
2.2.5 Disjunctive constraint
2.2.6 CUMULATIVE constraint
2.3 Polynomial time algorithms for scheduling problems
2.3.1 Related Work
2.3.2 Scheduling Graph
2.3.3 Network Flows
3 Filtering algorithms for the disjunctive and cumulative constraints
3.1 Overload Checking
3.2 Time-Tabling
3.3 Edge-Finding
3.3.1 (Θ − Λ)L−tree
3.4 Extended-Edge-Finding
3.5 Not-First/Not-Last
3.6 Energetic Reasoning
3.7 Detectable Precedences
3.8 Precedence Graph
3.9 Combination of filtering techniques
3.10 Filtering techniques in the state of the art schedulers
4 Linear time Algorithms for Disjunctive constraint
4.1 Preliminaries
4.1.1 Union-Find
4.2 Time-Tabling
4.3 The Time Line Data Structure
4.4 Overload Checking
4.5 Detectable Precedences
4.6 Experimental Results
Two sorting algorithms
Filtering algorithms
4.7 Minimizing maximum lateness and total delay
4.8 Conclusion
5 Overload Checking and Edge-Finding for Robust Cumulative Scheduling
5.1 Preliminaries and the general framework
5.1.1 Robust cumulative constraint
5.2 Robust Overload Checking
5.2.1 The general form of robust Overload Checking rule
5.2.2 Robust earliest energy envelope
5.2.3 Robust Overload Checking rule in terms of robust energy envelope
5.2.5 Robust Overload Checking algorithm
5.3 Robust Edge-Finding
5.3.1 Filtering the earliest starting times
Robust Edge-Finding rule for filtering the earliest starting times
Robust Λ−earliest energy envelope
Robust Edge-Finding algorithm for filtering the earliest starting times
5.3.2 Filtering the latest completion times
Robust Edge-Finding rules for filtering the latest completion times
Robust latest energy envelope
Robust Λ−latest energy envelope
Robust Edge-Finding algorithm for filtering the latest completion times
5.4 Experiments
5.5 Conclusion
6 Variants of Multi-Resource Scheduling Problems with Equal Processing Times
6.1 Variety of machine numbers through the time
6.2 General Objective Function
6.3 Scheduling problems with monotonic objective functions
6.4 Scheduling problems with periodic objective functions
6.4.1 Scheduling problem as a network flow
6.4.2 Periodic objective function formulated as a network flow
6.5 Minimizing maximum lateness
6.6 Conclusion
Conclusion

Télécharger le rapport complet