摘要
【目的】讨论带有多个工期窗口及退化维护的单机排序问题。【方法】工件的加工时间是一个和资源分配、工件在排序中的位置以及退化效应有关的凸函数。目标是确定多个最优工期窗口的位置和大小、指派给每个工期窗口的工件集合、分配给每个工件的资源、最优的维修位置和最优的工件排序,最小化提前、误工、工期窗口的开始时间、工期窗口的大小、资源分配、时间表长的总费用。【结果】证明了带有多个工期窗口及退化维护的单机排序问题仍然是多项式可解的。【结论】最优算法是可以在O(n4)时间内求出最优解。
[Purposes]It considers the multiple common due window assignment and single machine scheduling with a job-dependent aging effect and deteriorating maintenance activity. [Methods]It assumes that the processing time of a job is a convex function of the amount of a resource allocated to it, its position in the processing sequence, and its aging effect. The objective is to find the optimal due-window, the optimal maintenance position so as to minimize the total cost, which is a function of earliness, tardiness, due- window starting time, due-window size, resource consumption, makespan. [Findings]It shows that multiple due-window assignment and a deteriorating rate-modifying activity remains polynomial time solvable. [Conclusions]And it introduces an efficient O(n4) algorithm to solve the problem.
出处
《重庆师范大学学报(自然科学版)》
CAS
CSCD
北大核心
2017年第3期20-27,共8页
Journal of Chongqing Normal University:Natural Science
基金
国家自然科学基金(No.11171050)
辽宁省教育厅项目(No.L2014433)
关键词
单机排序
多工期窗口
可控加工时间
退化效应
退化维修
single machine scheduling
multiple common due windows
controllable processing times
aging effect
deterioratingrating-modifying activity