An Approximation Algorithm for the Parallel-Machine Customer Order Scheduling with Delivery Time and Submodular Rejection Penalties

In this paper,we consider the parallel-machine customer order scheduling with delivery time and submodular rejection penalties.In this problem,we are given m dedicated machines in parallel and n customer orders.Each order has a delivery time and consists of m product types and each product type should be manufactured on a dedicated machine.An order is either rejected,in which case a rejection penalty has to be paid,or accepted and manufactured on the m dedicated machines.The objective is to find a solution to minimize the sum of the maximum delivery completion time of the accepted orders and the penalty of the rejected orders which is determined by a submodular function.We design an LP rounding algorithm with approximation ratio of n+1 for this problem.

ORDER SCHEDULING WITH CONTROLLABLE PROCESSING TIMES, COMMON DUE DATE AND THE PROCESSING DEADLINE

Due date quotation and scheduling are important tools to match demand with production capacity in the MTO （make-to-order） environment. We consider an order scheduling problem faced by a manufacturing f＇trm operating in an MTO environment, where the firm needs to quote a common due date for the customers, and simultaneously control the processing times of customer orders （by allocating extra resources to process the orders） so as to complete the orders before a given deadline. The objective is to minimize the total costs of earliness, tardiness, due date assignment and extra resource consumption. We show the problem is NP-hard, even if the cost weights for controlling the order processing times are identical. We identify several polynomially solvable cases of the problem, and develop a branch and bound algorithm and three Tabu search algorithms to solve the general problem. We then conduct computational experiments to evaluate the performance of the three Tabu-search algorithms and show that they are generally effective in terms of solution quality.

A Trip-Chain Based User Equilibrium Traffic Assignment Model with Flexible Activities Scheduling Order

This study developed a user equilibrium traffic assignment model based on trip-chains with flexible activity scheduling order and derived the corresponding optimality conditions. We based on the gradient projection method to develop a solution algorithm, the accuracy of which was verified using the test network of UTown. This model could be used to estimate the transportation demands with and without activities scheduling restriction between OD （origin-destination） pairs based on trip-chains, as well as based on trips. Thus, the proposed model is more generalization than conventional trip based or trip-chain based traffic assignment models.

Rule-based scheduling of multi-stage multi-product batch plants with parallel units

A novel rule-based model for multi-stage multi-product scheduling problem(MMSP)in batch plants with parallel units is proposed.The scheduling problem is decomposed into two sub-problems of order assignment and order sequencing.Firstly,hierarchical scheduling strategy is presented for solving the former sub-problem,where the multi-stage multi-product batch process is divided into multiple sequentially connected single process stages,and then the production of orders are arranged in each single stage by using forward order assignment strategy and backward order assignment strategy respectively according to the feature of scheduling objective.Line-up competition algorithm(LCA)is presented to find out optimal order sequence and order assignment rule,which can minimize total flow time or maximize total weighted process time.Computational results show that the proposed approach can obtain better solutions than those of the literature for all scheduling problems with more than 10 orders.Moreover,with the problem size increasing,the solutions obtained by the proposed approach are improved remarkably.The proposed approach has the potential to solve large size MMSP.

Reducing unnecessary crossmatching for hip fracture patients by accounting for preoperative hemoglobin concentration

BACKGROUND Maximum surgical blood order schedules were designed to eliminate unnecessary preoperative crossmatching prior to surgery in order to conserve blood bank resources.Most protocols recommend type and cross of 2 red blood cell(RBC)units for patients undergoing surgery for treatment of hip fracture.Preoperative hemoglobin has been identified as the strongest predictor of inpatient transfusion,but current maximum surgical blood order schedules do not consider preoperative hemoglobin values to determine the number of RBC units to prepare prior to surgery.AIM To determine the preoperative hemoglobin level resulting in the optimal 2:1 crossmatch-to-transfusion(C:T)ratio in hip fracture surgery patients.METHODS In 2015 a patient blood management(PBM)program was implemented at our institution mandating a single unit-per-occurrence transfusion policy and a restrictive transfusion threshold of<7 g/dL hemoglobin in asymptomatic patients and<8 g/dL in those with refractory symptomatic anemia or history of coronary artery disease.We identified all hip fracture patients between 2013 and 2017 and compared the preoperative hemoglobin which would predict a 2:1 C:T ratio in the pre PBM and post PBM cohorts.Prediction profiling and sensitivity analysis were performed with statistical significance set at P<0.05.RESULTS Four hundred and ninety-eight patients who underwent hip fracture surgery between 2013 and 2017 were identified,291 in the post PBM cohort.Transfusion requirements in the post PBM cohort were lower(51%vs 33%,P<0.0001)than in the pre PBM cohort.The mean RBC units transfused per patient was 1.15 in the pre PBM cohort,compared to 0.66 in the post PBM cohort(P<0.001).The 2:1 C:T ratio(inpatient transfusion probability of 50%)was predicted by a preoperative hemoglobin of 12.3 g/dL[area under the curve(AUC)0.78(95%confidence interval(CI),0.72-0.83),Sensitivity 0.66]in the pre PBM cohort and 10.7 g/dL[AUC 0.78(95%CI,0.73-0.83),Sensitivity 0.88]in the post PBM cohort.A 50%probability of requiring>1 RBC unit was predicted by 11.2g/dL[AUC 0.80(95%CI,0.74-0.85),Sensitivity 0.87]in the pre PBM cohort and 8.7g/dL[AUC 0.78(95%CI,0.73-0.83),Sensitivity 0.84]in the post-PBM cohort.CONCLUSION The hip fracture maximum surgical blood order schedule should consider preoperative hemoglobin in determining the number of units to type and cross prior to surgery.