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

1/--страниц