Some Coordinated Scheduling Problems With Delivery

Scheduling theory is an important research field of combinatorial optimiza-tion. Since its extensive applicable background and great theoretical significance, the scheduling theory has been applied in many areas, such as military, economy, transportation, management and computer science, etc. The scheduling problems of coordinated production and delivery were derived from processing jobs on the big industry lathe, has an amazing practical value in logistics and supply chain management. Many research results were presented. Batch scheduling, schedul-ing with learning effect, scheduling with incompatible families, and scheduling with outsourced distribution are relatively new scheduling models, which have received great attention from researchers both at home and abroad. In this dis-sertation, we discuss some scheduling problems of above types. The main results are provided as follows.1. In Chapter Ⅰ, we introduce some basic definitions, notation and funda-mental knowledge of scheduling.2. We consider a coordinated scheduling problem of transportation and se-rial batching in Chapter Ⅱ. The objectives are minimizing the sum of the jobs’ total completion time and the total processing cost and minimizing the sum of the makespan and the total processing cost respectively. Under the condition of the job processing times are equal, if the job assignment to the vehicles is pre-determined, we respectively provide the polynomial time dynamic programming algorithms, for the general problems, prove that they are NP-hard. When the returning time of vehicle is 0, we present the approximation algorithms and prove that the worst case ratio of the algorithms are 2-1/m.3. In Chapter Ⅲ, we discuss the problem of minimizing the weighted num-ber of tardy jobs on a single batch processing machine, where the jobs are par-titioned into F incompatible families and the jobs in each family have the com-mon processing time and the common weight. The objective is minimizing the weighted number of tardy jobs. When the family number F is fixed, we first present a pseudo-polynomial time algorithm with running time O(bF12Fn2FW) and an fully polynomial time approximation scheme, where b is the batch ca-pacity. If the jobs in each family also have the same due date, we devise an O(n(log n+W min{P, dmax}))-time algorithm, where P, W are respectively the total processing times and the total weights of the jobs, dmax is the maximal due date.4. In Chapter IV, we research the coordination problem of scheduling and batch deliveries with learning effect. Along with the increase of jobs processed on machine, machine has the certain leaning ability. The actual job processing time is a function of the sum of the logarithm of the processing times of the jobs already processed, i.e., pj[r]=pj(1+Σ(r-1)(l=1)lnp[l])α,is the actual job processing time of job j on the r-th position, p[i] is the original processing time of the l-th job, and α≤0 is the learning effect. The objectives are minimizing the sum of the jobs’ total delivery time and the total delivery cost and minimizing the sum of the maximal lateness and the total delivery cost respectively. We give the dynamic programming algorithms with running times O(n4) and O(n5) respectively.5. In chapter V, we study coordinated production and outsourced batch de-livery scheduling problems with three transportation models, where a third-party logistics provider delivers the jobs at middle stage, the jobs must be delivered by batching within a time T from their release at the upstream stage. Three trans-portation models are respectively normal transportation, express transportation and immediate transportation, the objective is minimizing the transportation cost. When manufacturer dominates, if there is only normal transportation or express transportation, we present a polynomial time algorithm with running time O(nL), where L is the number of the vehicles departure times. If there are normal transportation and express transportation, when there is an unlimit-ed number of vehicles for express transportation, we present a polynomial time algorithm with running time O(n3L2c2(L1+L2)(L1+L2+c2)); when there is a limited number of vehicles for express transportation, we present a polynomial time algorithm with running time O(n3c2(L1+V1)(L2+V2)(L1+V1+c2)). If there are three transportation models, when there is an unlimited number of vehicles for immediate transportation, we present a polynomial time algorithm with run- ning time O(n4L1L1V1V2c3(L1V1+L2V2+c3)); when there is a limited number of vehicles for immediate transportation, we present a polynomial time algorith-m with running time O(n2V3+4L1L2V1V2c3(L1V1+L2V2)+n2V3+6L1L2V1V2c23), where L1, L2 are the numbers of the normal and express transportation vehicles departure times respectively, Vi, ci (i=1,2,3) is respectively the vehicles num-ber and capacity of normal, express and immediate transportation. When the third-part logistics provider dominates, the scheduling problem is strongly MP-hard.