Patent ID: 8073726

Claim:
A method for allocating crew members, comprising: identifying a plurality of legs; identifying a first broken crew and a first sequence associated with a first broken leg of the plurality of legs; identifying a second broken crew and a second sequence associated with a second broken leg of the plurality of legs; generating a plurality of new sequences for the first broken crew and the second broken crew using deadheads; and generating, using one or more computers, a solution for each of the first and second broken crews using a mixed integer program, the mixed integer program comprising a problem represented by: minimize s â¡ ( x , y , z ) = âˆ‘ i âˆˆ T â¢ âˆ‘ k âˆˆ P â¡ ( i ) â¢ c i , k â¢ x i , k + âˆ‘ j âˆˆ F â¢ ( cA j â¢ y j + cB j â¢ z j ) , ( 1 ) subject to: âˆ‘ i âˆˆ T â¢ âˆ‘ k âˆˆ P â¡ ( i ) â¢ Î´ i , k , j â¢ x i , k - z j + y j = m j â¢ â¢ ( j âˆˆ F ) ; ( 2 ) âˆ‘ k âˆˆ P â¡ ( i ) â¢ x i , k = 1 â¢ â¢ ( âˆ€ i âˆˆ T ) ; ( 3 ) z j â‰§0 and integer( jÎµF )â€ƒâ€ƒ(4) y j â‰§0 and integer( jÎµF ); andâ€ƒâ€ƒ(5) x i,k â‰§0 and integer(âˆ€ iÎµT;âˆ€kÎµP ( i ));â€ƒâ€ƒ(6) where T is a set of the broken crews; where F is a set of operational legs to be covered; where P (i) is a set of the new sequences which a broken crew i can work; where Î´ i,k,j is an indicator with value 1 when a sequence k for the broken crew i covers an operational leg j and 0 otherwise; where m j is a number of crews required by contract, business, or government rules for the operational leg j according to its fleet type; where c i,k is a cost of the sequence k for the broken crew i; where cA j is a first penalty cost associated with not covering the operational leg j; where a cB j is a second penalty cost associated with the operational leg j overlapped; where x i,k is a binary decision variable with value 1 when the broken crew i flies the sequence k and 0 otherwise; where y j is a slack variable for problem feasibility associated with the operational leg j; and where z j is a surplus variable associated with the operational leg j.