Privacy becomes a more serious concern in applications involving microdata such as medical data publishing or medical data mining. Anonymization methods based on global recoding or local recoding or clustering provide privacy protection by guaranteeing that each released record will be indistinguishable to some other individual. However, such methods may not always achieve effective anonymization in terms of analysis workload using the anonymized data. The utility of attributes has not been well considered in the previous methods. This paper studies the problem of utility-based anonymization to concentrate on attributes order sensitive workload, where the order of the attributes is important to the analysis workload. Based on the multidimensional anonymization concept, a method is discussed for attributes order sensitive utility-based anonymization. The performance study using public data sets shows that the efficiency is not affected by the attributes order processing.