沈阳师范大学学报（自然科学版）
瀋暘師範大學學報（自然科學版）
침양사범대학학보（자연과학판）
Journal of Shenyang Normal University (Natural Science Edition)
2015年
3期
358-364
,共7页
单机%排序%学习效应%退化效应%拒绝
單機%排序%學習效應%退化效應%拒絕
단궤%배서%학습효응%퇴화효응%거절
single machine%scheduling%learning effect%deterioration effect%rej ection
讨论了具有学习效应和退化效应的多窗口的可拒绝单机排序问题。工件的实际加工时间与开始加工时间和所排位置有关。工件集分为接受工件集和拒绝工件集，对于被拒绝加工的工件而言，它的费用只与工件有关，目标是确定接受工件集的最优加工顺序和拒绝费用，从而极小化2个费用函数。考虑2个问题，第1个问题的目标函数是与提前、延误、窗口的开始时间、窗口的大小以及拒绝费用有关的函数，第2个问题的目标函数是与提前、延误工件数、窗口的开始时间、窗口的大小以及拒绝费用有关的函数，并且针对这2个问题分别给出了多项式时间算法。
討論瞭具有學習效應和退化效應的多窗口的可拒絕單機排序問題。工件的實際加工時間與開始加工時間和所排位置有關。工件集分為接受工件集和拒絕工件集，對于被拒絕加工的工件而言，它的費用隻與工件有關，目標是確定接受工件集的最優加工順序和拒絕費用，從而極小化2箇費用函數。攷慮2箇問題，第1箇問題的目標函數是與提前、延誤、窗口的開始時間、窗口的大小以及拒絕費用有關的函數，第2箇問題的目標函數是與提前、延誤工件數、窗口的開始時間、窗口的大小以及拒絕費用有關的函數，併且針對這2箇問題分彆給齣瞭多項式時間算法。
토론료구유학습효응화퇴화효응적다창구적가거절단궤배서문제。공건적실제가공시간여개시가공시간화소배위치유관。공건집분위접수공건집화거절공건집，대우피거절가공적공건이언，타적비용지여공건유관，목표시학정접수공건집적최우가공순서화거절비용，종이겁소화2개비용함수。고필2개문제，제1개문제적목표함수시여제전、연오、창구적개시시간、창구적대소이급거절비용유관적함수，제2개문제적목표함수시여제전、연오공건수、창구적개시시간、창구적대소이급거절비용유관적함수，병차침대저2개문제분별급출료다항식시간산법。
We discuss single machine scheduling with both learning and deterioration effects and rej ection,in which the jobs have multiple due windows.The actual processing time of accepted jobs is a function of its starting time and position in a sequence.We solve the problem by partitioning the jobs into a set of accepted and a set of rejected jobs.The objective is to determine the optimal sequence of accepted jobs and the cost of the rejected jobs,so as to minimize the total costs. We consider two versions of the problem.For the first version,the total cost includes earliness,tardiness,the starting time of due windows,the size of due windows and rej ection cost.For the second version,it includes earliness,the number of tardy jobs,the starting time of due windows,the size of due windows and rejection cost.We present polynomial algorithms for two versions,respectively.
