具有学习效应且交货期可指派的单机排序问题

Single Machine Scheduling with Due Date Assignment and Learning Effects

探讨了工件具有CON/SLK交货期指派且机器具有与位置有关的学习效应目标为极小化交货期指派费用、无误工工件的提前费用以及误工工件的惩罚费用之和排序问题.所探讨的问题在无误工工件数确定的情况下可以转化为指派问题,由于误工工件数最多有n种可能且指派问题能在O(n3)时间内解决,故排序问题是多项式时间可解的,并给出最优算法;在恶化工件具有CON/SLK交货期指派的基础上同时考虑了机器具有学习效应的排序,并给出了两种问题的多项式时间最优算法.

This paper considers the problems of scheduling a single machine with position -dependent learning effects and CON/SLK due date assignment to minimize costs for due date assignment,earliness and penalties of tardy jobs. If the number of non- tardy jobs is fixed,the problems considered can be for- mulated as assignment problems. The assignment problem is solved in O（n3） time and different number of non- tardy jobs is at most n,so the problems can be solved in polynomial time and present optimal al- gorithms. Finally,basing on the scheduling deteriorating jobs with CON/SLK due date assignment,we consider the scheduling with learning effects simultaneously and present polynomial - time optimal algo- rithms to solve the problems.