We consider a network of parallel service stations each modelled as a single server queue. Each station serves its own dedicated customers as well as generic customers who are routed from a central controller. We suppose that the cost incurred by a customer is an increasing function of her time spent in system. In a significant advance on most previous work, we do not require waiting costs to be convex, still less linear. With the objective of minimizing the long-run average cost, we develop heuristic routing policies and demonstrate their superior performance in an extensive numerical study.