Single Machine Scheduling Problem With Public Delivery Window Assignment

With the wide application of the JIT system, common due window assignment problem has become a very active area of research. The common due window is to be determined, i.e. the starting time and size of due window both are variable. All jobs are available at zero, and job preemption is not allowed. The machine can only process one job at a time, finished jobs are delivered to the client, and the cost of one batch is fixed. We should determine the job sequence, common due window to minimize the total cost. On the one hand, in reality manufacturer will reject the order when an order takes a long time but with little profit. On the other hand, we can consider this kind of problem based on learning effect. So we respectively consider these two aspects to study the different problems:(1) Single-machine common due window assignment and scheduling with learning effectWe consider a single-machine scheduling problem with learning effect in which all jobs have an assignable common due window. If the jobs are processed in accordance with a certain permutation π=(J1,J2,…,Jn), the job Jr is sequenced in the r-th position, then the processing time of job Jr, pjr= pjra, where a is the learning factors (a< 0). The objective is to determine a job sequence, the due window to minimize the total cost comprising earliness, tardiness, starting time and size of the due window. We present a polynomial time algorithm.(2) Single-machine common due window assignment and scheduling with rejectionWe consider a single-machine scheduling problem with rejection in which all jobs have an assignable common due window. Finished jobs are delivered one by one, and the cost is fixed. The objective is to determine a job sequence accepted, the due window to minimize the total cost comprising earliness, tardiness, starting time and size of the due window, and delivery cost. We present a dynamic programming algorithm, and the algorithm is polynomial solvable.(3) Single-machine common due window assignment and scheduling with holding time limit to minimize the total costWe consider a batch delivery single-machine scheduling problem with holding time limit in which all jobs have an assignable common due window. The starting time and size of the due window are decision variables.Finished jobs are delivered in batches with unlimited batch capacity, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to determine a job sequence, a delivery date for each batch, and a starting time and a size for the due window to minimize the total cost comprising earliness, weighted number of tardy jobs, job holding, starting time and size of the due window, and batch delivery. We proof the problem with the holding time limit is at least ordinary NP-hardness.