Abstract

The Bellman-Johnson problem of the optimal policy for serving n units by m servers is considered. For an arbitrary (m ×n)-matrix B= ‖b _ij ‖ with real elements b _ij the logical determinant, i.e., the extremum characterization of B, is introduced in terms of using the elements expressed b _ij and using the operations + and max. The (m ×n)-matrix A=‖a _ij ‖ of service times, where a _ij is the j-th unit by the i-th server. is introduced as well. A family of mixed optimality conditions C is described which can be characterized as optimality conditions between necessary (H) and sufficient (D) ones. It is shown, that the optimal serving policy can be found with lower computional effort by using C under computational efforts in comparison by using conditions D and H.

Keywords:

• Serving system
• optimal serving policy
• mixed optimality conditions
• logical determinant

AMS 1980 Subject Classification:

• Primary; 90 B 30
• Secondary: 90 B 35