Забыли?

?

# Introduction to Job Shop Scheduling Problem

код для вставкиСкачать
```Introduction to Job Shop
Scheduling Problem
Qianjun Xu
Oct. 30, 2001
Description of Job Shop Scheduling
вЂў
вЂў
вЂў
вЂў
вЂў
A finite set of n jobs
Each job consists of a chain of operations
A finite set of m machines
Each machine can handle at most one operation at a time
Each operation needs to be processed during an
uninterrupted period of a given length on a given machine
вЂў Purpose is to find a schedule, that is, an allocation of the
operations to time intervals to machines, that has minimal
length
Formal Definition of JSS
J пЂЅ { j1 , j 2 , ... j n }
Job set
M пЂЅ { m1 , m 2 , ... m m }
Machine set
O i пЂЅ { o i1 , o i 2 ,... o im }
Operations
O пЂЅ {o1 , o 2 , ... o n }
Each operation has processing time {пЃґ i1 , пЃґ i 2 ,...пЃґ im }
On O define A, a binary relation represent a precedence
between operations. If ( v , w ) пѓЋ A then v has to be
performed before w.
вЂў A induce the total ordering belonging to the same job; no
precedence exist between operations of different jobs.
вЂў
вЂў
вЂў
вЂў
вЂў
i
i
Formal Definition of JSS cont.
вЂў A schedule is a function S : O п‚® IN пѓ€ { 0 } that for each operation v
defines a start time S(v).
вЂў A schedule S is feasible if
пЂўv пѓЋ O :
S (v ) п‚і 0
пЂў v, w пѓЋ O , (v, w ) пѓЋ A :
S (v ) пЂ« пЃґ (v ) п‚Ј S ( w )
пЂў v , w пѓЋ O , v п‚№ w , M ( v ) пЂЅ M ( w ) : S ( v ) пЂ« пЃґ ( v ) п‚Ј S ( w ) or
S ( w ) пЂ« пЃґ ( w ) п‚Ј S (v )
вЂў The length of a schedule S is len ( S ) пЂЅ max v пѓЋ O ( S ( v ) пЂ« пЃґ ( v ) )
вЂў The goal is to find an optimal schedule, a feasible schedule of
minimum length., min(len(S)).
Disjunctive Graph
вЂў An instance of the JSS problem can be represented by
means of a disjunctive graph G=(O, A, E).
вЂў The vertices in O represent the operations
вЂў The arcs in A represent the given precedence between the
operations
вЂў The edge in E пЂЅ { ( v , w ) v , w пѓЋ O , v п‚№ w , M ( v ) пЂЅ M ( w ) }
represent the machine capacity constraints
вЂў Each vertex v has a weight, equal to the processing time
пЃґ (v )
Example of Disjunctive Graph
Disjunctive Graph with Edge
Orientations
Disjunctive Graph Cont.
вЂў Finding an optimal feasible schedule is equivalent to
finding an orientation EвЂ™ that minimizes the longest path
length in the related digraph.
Why JSS Problem
вЂў It is considered to be a good representation of the general
domain and has earned a reputation for being notoriously
difficult to solve
вЂў JSS is considered to belong to the class of decision
problems which are NP
вЂў Lenstra et al(1977) Show that
вЂ“ 3*3 problem
вЂ“ N*2 instance with no more than 3 operations per job
вЂ“ N*3 problem with no more than 2 operations per job
вЂ“ N*3 problem where all operations are of unit processing time
Belong to the set of NP instances.
Methods to Solve JSS
вЂў Mathematical Formulations:
вЂ“ mixed integer linear programming (1960)
вЂў Branch and Bound
вЂў Approximation Methods
вЂ“ Priority dispatch rules
вЂ“ Bottleneck based heuristics
вЂ“ Artificial intelligence(constraint satisfaction approach,
neural networks)
вЂ“ Local search methods
Branch and Bound
вЂў Using a dynamically constructed tree structure represents the solution
space of all feasible sequences
вЂў Search begins at topmost node and a complete selection is achieved
once the lowest level node has been evaluated
вЂў Each node at a level p in the search tree represent a partial sequence of
p operations
вЂў From an unselected node the branching operation determines the next
set of possible nodes from which the search could progress
вЂў The bounding procedure selects the operation which will continue the
search and is based on an estimated LB and currently best achieved
UB. IF at any node the estimated LB is found to be greater than the
current best UB, this partial selection and all its subsequent
descendants are disregarded.
Priority Dispatch Rules
вЂў At each successive step all the operations which are
available to be scheduled are assigned a priority and the
operation with the highest priority is chosen to be
sequenced.
вЂў Usually several runs of PDRs are made in order to achieve
valid results.
Constraint Satisfaction Approach
вЂў Aiming at reducing the effective size of the search space
by applying constraints that restrict the order in which
variables are selected and the sequence in which possible
values are assigned to each variable
вЂў Constraint propagation
вЂў Backtracking
вЂў Variable heuristic
вЂў Value heuristic
Neural Networks
вЂў Hopfield networks
вЂў Back-error propagation networks
Local Search Method
вЂў Configurations: a finite set of solutions.
вЂў Cost function to be optimised.
вЂў Generation mechanism, generating a transition from one
configuration to another.
вЂў Neighborhood, N(x), is a function which defines a simple
transition from a solution x to another solution by inducing
a change.
вЂў Selection of neighborhood:
вЂ“ chose the first lower cost neighbor found;
вЂ“ select the best neighbor in the entire neighborhood;
вЂ“ Choose the best of a sample of neighbors.
Summary
вЂў The definition of JSS
вЂў The disjunctive graph
вЂў The methods to solve JSS
```
###### Документ
Категория
Презентации
Просмотров
15
Размер файла
76 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа