Custom post type permalink structure to include the taxonomy

Try this

   $args['rewrite']=array('slug'=>'/%my_service_cats%/');
    register_post_type( 'my_services', $args);
    register_taxonomy( 'my_service_cats', 'my_services', $args);