多共同工期分配调度问题算法研究  

An Algorithm for Multiple Common Due-Date Assignments Scheduling Problem

作　　者：包晗 吕丹阳 王吉波 BAO Han;LYU Danyang;WANG Jibo(School of Science,Shenyang Aerospace University,Shenyang 110136,China)

机构地区：[1]沈阳航空航天大学理学院,沈阳110136

出　　处：《重庆师范大学学报（自然科学版）》2024年第1期8-13,共6页Journal of Chongqing Normal University:Natural Science

基　　金：国家自然科学基金(No.71471120);辽宁省“兴辽英才计划”项目资助(No.XLYC2002017)。

摘　　要：为确定所有工件的多个共同工期以及工件的最优调度序列,最小化提前惩罚、延误惩罚和公共工期分配的加权和,利用位置权重与处理时间的匹配过程来获得最优解。对此问题给出了最优解满足的性质,当分配给共同工期的工件个数为给定常数时该问题可解。该问题是多项式可解的,并给出了具体求解算法。The goal is to determine multiple common durations for all jobs as well as an optimal scheduling sequence for the jobs that minimizes the weighted sum of the earliness penalties,lateness penalties,and common due date assignments.The matching process of position weight and processing time is used to obtain the optimal solution.This problem can be solved when the number of jobs assigned to the common due date is given a constant.The problem is polynomially solvable and a specific solution algorithm is given.

关 键 词：调度 提前/延误惩罚 多项式时间算法 单机 多共同工期 

分 类 号：O221.6[理学—运筹学与控制论]