This paper studies a problem encountered by a buying office for one of the largest retail distributors in the world. An important task for the buying office is to plan the distribution of goods from Asia to various destinations across Europe. The goods are transported along shipping lanes by shipping companies, which offer different discount rates depending on the freight quantity. To increase the reliability of transportation, the shipper imposes a quantity limit on each shipping company on each shipping lane. To guarantee a minimum business volume, each shipping company requests a minimum total freight quantity over all lanes if it is contracted. The task involves allocating projected demand of each shipping lane to shipping companies subject to the above conditions such that the total cost is minimized.Existing work on this and related problems employs commercial linear programming software to solve their models. However, since the problem is NP−hard in the strong sense, it is unlikely to be solvable optimally in reasonable time for large cases. Hence, we propose the first heuristic-based algorithm for the problem, which combines a filter-and-fan search scheme with a tabu search mechanism. Experiments on randomly generated test instances show that as the size of the problem increases, our algorithm produces superior solutions in less time compared to a leading mixed-integer programming solver. 相似文献
A simple approach for analyzing longitudinally measured biomarkers is to calculate summary measures such as the area under the curve (AUC) for each individual and then compare the mean AUC between treatment groups using methods such as t test. This two-step approach is difficult to implement when there are missing data since the AUC cannot be directly calculated for individuals with missing measurements. Simple methods for dealing with missing data include the complete case analysis and imputation. A recent study showed that the estimated mean AUC difference between treatment groups based on the linear mixed model (LMM), rather than on individually calculated AUCs by simple imputation, has negligible bias under random missing assumptions and only small bias when missing is not at random. However, this model assumes the outcome to be normally distributed, which is often violated in biomarker data. In this paper, we propose to use a LMM on log-transformed biomarkers, based on which statistical inference for the ratio, rather than difference, of AUC between treatment groups is provided. The proposed method can not only handle the potential baseline imbalance in a randomized trail but also circumvent the estimation of the nuisance variance parameters in the log-normal model. The proposed model is applied to a recently completed large randomized trial studying the effect of nicotine reduction on biomarker exposure of smokers. 相似文献
In the multiprocessor scheduling problem to minimize the total job completion time, an optimal schedule can be obtained by the shortest processing time rule and the completion time of each job in the schedule can be used as a guarantee for scheduling revenue. However, in practice, some jobs will not arrive at the beginning of the schedule but are delayed and their delayed arrival times are given to the decision-maker for possible rescheduling. The decision-maker can choose to reject some jobs in order to minimize the total operational cost that includes three cost components: the total rejection cost of the rejected jobs, the total completion time of the accepted jobs, and the penalty on the maximum tardiness for the accepted jobs, for which their completion times in the planned schedule are their virtual due dates. This novel rescheduling problem generalizes several classic NP-hard scheduling problems. We first design a pseudo-polynomial time dynamic programming exact algorithm and then, when the tardiness can be unbounded, we develop it into a fully polynomial time approximation scheme. The dynamic programming exact algorithm has a space complexity too high for truthful implementation; we propose an alternative to integrate the enumeration and the dynamic programming recurrences, followed by a depth-first-search walk in the reschedule space. We implemented the alternative exact algorithm in C and conducted numerical experiments to demonstrate its promising performance.