带速率修改活动且工件加工时间离散可控下的排序问题研究

发布时间：2018-07-02 21:30

本文选题：排序 + 速率修改活动　；参考：《宁波大学》2017年硕士论文

【摘要】：组合优化是运筹学和理论计算机科学的一个重要分支,其中,人们热衷于讨论的一个方向便是排序问题.一般排序模型是在一定的工件特征和机器环境下考虑的.近年来,随着实际生产需求的不断提高和改变,逐渐衍生出一些新的排序问题.针对工件特征,人们研究工件加工时间可控或者不可控的问题.针对机器环境,人们研究机器需要速率修改活动情形下的排序问题.速率修改活动有两个关键的参数,进行活动的开始时间和活动持续的时长.不同要求下的参数对应着不同的排序问题.围绕上述两点进行展开,本文主要讨论了下面两类新型排序问题:带速率修改活动且工件加工时间离散可控下的单机排序问题和带速率修改活动且工件加工时间离散可控下的平行机排序问题.全文共分为四章:第一章的绪论中主要介绍了组合优化问题,排序问题及计算复杂性的基本概念和相关知识,系统的总结了国内外研究现状和发展趋势.第二章研究了带速率修改活动且工件加工时间离散可控下的单机排序问题,其中速率修改活动的时长是其开始时刻的非降函数.将给定的n个独立工件J= {J1,J2,…,Jn}安排在一台机器上进行加工,每个工件有多个加工时间可选,当工件的加工时间不同时,其对应的加工成本也不相同.此外,我们对机器是否进行速率修改活动分情况进行讨论,目标是找到所有工件的最优排序,确定每个工件的加工时间,加工成本及速率修改活动的开始时间,使得目标函数的值最小.当极小化目标函数是最大完工时间加总加工成本时,给出多项式时间的精确算法.当极小化目标函数分别是完工时间和加总加工成本,提前延迟与截止时间惩罚和加总加工成本时,也分别设计了计算复杂度均为O(n4m)的多项式时间精确算法.第三章对第二章的内容进行了拓展,考虑的是带速率修改活动且工件加工时间离散可控的平行机排序问题,将给定的有n个独立工件的工件集J = {J1, J2,..., Jn}安排在m (m n)台机器(Mi,i= 1,2,…,m)上加工,所有工件在0时刻同时到达.每个工件在每台机器上都有多个加工时间可选择.目标仍是给出所有工件的最优排序,确定每个工件的加工时间,加工成本及速率修改活动的开始时间,使得目标函数的值最小.当极小化目标函数是最大完工时间加总加工成本时,给出计算复杂度是O(mkn)的算法.当极小化目标函数是机器总负载加总加工成本时,给出计算复杂度是O(nm|+4)的算法,当极小化目标函数提前与延误的惩罚和加总加工成本时,给出计算复杂度是O(mkn2 + nm+4)的算法.第四章对全文进行了总结,并给出了今后仍需继续探索的方向和内容。
[Abstract]:Combinatorial optimization is an important branch of Computer Science in operational research and theory. One of the directions that people are keen on is the sort problem. The general ordering model is considered under certain job features and machine environment. In recent years, with the continuous improvement and change of actual production demand, some new sorts are gradually derived. Problem. In view of the feature of the workpiece, people study the problem of controllable or uncontrollable processing time of the workpiece. In the machine environment, people study the sorting problem under the condition of rate modification. Rate modification activities have two key parameters, starting time of activity and duration of activity. The corresponding parameters are corresponding to different requirements. In this paper, the following two kinds of new sorting problems are discussed in this paper: single machine scheduling with rate modification activities, single machine scheduling with discrete processing time of the workpiece and parallel machine scheduling with rate modification activities and discrete processing time of work pieces. The full text is divided into four chapters: first In the introduction of the chapter, the basic concepts and related knowledge of combinatorial optimization, sorting and computing complexity are introduced, and the research status and development trend at home and abroad are summarized systematically. The second chapter studies the single machine sorting problem with rate modification activities and the discrete-time controllable processing time of the workpiece, in which the rate modification activity is long The non decreasing function of its starting time. The given n independent jobs J= {J1, J2,... Jn} is arranged on a machine. Each workpiece has multiple processing times. When the working time of the workpiece is different, the corresponding processing cost is different. In addition, we discuss the rate modification activities of the machine. The goal is to find the optimal order of all the workpieces and determine the processing of each workpiece. When the minimum target function is the maximum completion time and the total processing cost, the exact algorithm of polynomial time is given. When the minimization target function is the completion time and the total processing cost, the advance delay and the deadline penalty and the sum of the total processing cost are respectively. At the cost of processing, a polynomial time precise algorithm for calculating the complexity of O (n4m) is also designed. The third chapter extends the content of the second chapter, considering the parallel machine sorting problem with the rate modification activity and the discrete processing time of the workpiece. The set of artifacts with a given n independent workpiece is J = {J1, J2,..., Jn} arrangement. On the M (m n) machine (Mi, i= 1,2,... M) is processed, all work pieces arrive at the same time at the same time at 0 time. Each workpiece has multiple processing times on each machine. The target still gives the optimal order of all the workpieces, determines the processing time of each workpiece, the processing cost and rate changes the start time of the activity, making the target function minimum. When minimizing the target function, When the maximum completion time is added to the total processing cost, the calculation complexity is an algorithm of O (MKN). When the minimization objective function is the total machine load plus the total processing cost, the calculation complexity is an algorithm of O (nm|+4). When the penalty and total processing cost of the target function are minimized and the total processing cost is minimized, the computational complexity is O (mkn2 + nm+4). The fourth chapter summarizes the full text and gives directions and contents to be explored in the future.
【学位授予单位】：宁波大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O223

【相似文献】