具有相同批容量和相同工期的单机准时分批排序问题

Single Machine Batch Just-in-time Scheduling Problems with Common Batch Size and Common Due Date of Jobs

研究具有相同批容量和相同工期的单机准时分批排序问题.这里相同批容量是指每批加工的工件数相同且恰为b个.准时排序要求工件在工期准时完工,提前或误工均受到惩罚.在两种分批方式下进行排序:继列分批和平行分批.目标函数为最小化加权总绝对误差和加权非准时惩罚.这里的权重不是工件自身所拥有的,而是工件所在的批一旦排在某个位置所获得的位置权重.证明了这些问题均可在O(nlogn)时间内解决.

In this paper, the single machine, common due date, common batch size, batching Just-In-Time scheduling problems are discussed. Common batch size means that each batch contains exactly b jobs. Just-In-Time means that all jobs must be completed exactly on their assigned due dates, otherwise penalty must be executed, both for earliness and tardiness. Batch-scheduling include two kinds of models： the serial-batch scheduling and the parallel- batch scheduling. The objectives are to minimize the weighted total absolute deviation and the weighted earliness-tardiness. The weights are not the weights of jobs but the batch-position weights of scheduled batches which include the jobs. It is showed that each of these problems can be solved in O（n log n） time.