带有安装时间的单机成组排序问题的开题报告.docx

带有安装时间的单机成组排序问题的开题报告
题目：带有安装时间的单机成组排序问题
一、研究背景
单机成组排序（SingleMachineGroupScheduling，SMGS）问题是组合优化领域中经典的NP-hard问题，已被广泛研究。SMGS问题要求将$n$个不同的工作分配到$m$个工作组，且每个工作组中的工作必须按照非递减的顺序进行处理，即同一工作组中的工作必须以相同的次序处理。现有的研究假设所有工作可以同时启动，忽略了工作的安装时间，即工作在安装后才可以被启动。
然而，在实际应用中，很多工作需要先安装后才能被启动。例如，在生产线上，机器需要安装加工刀具才能进行加工，而加工刀具的安装时间是不可忽略的。因此，SMGS问题需要考虑每个工作的安装时间，以便实现更准确的工作调度。
二、研究内容
本文旨在研究带有安装时间的单机成组排序问题。具体内容包括：
1.研究带有安装时间的单机成组排序问题的算法设计和实现，探究不同的启发式算法在该问题中的效果。
2.比较带有安装时间的单机成组排序问题与经典的SMGS问题的异同，分析添加安装时间对问题求解的影响，并探究如何更好地在SMGS问题中添加安装时间。
3.对实际生产线中的工作调度问题进行分析，并以SMGS问题为基础，研究如何将理论研究应用于实际生产过程中，从而提高生产效率。
三、研究方法和技术路线
本文将采用启发式算法研究带有安装时间的单机成组排序问题。主要包括模拟退火算法、遗传算法、禁忌搜索算法、粒子群优化算法等。
技术路线如下：
1.首先研究经典SMGS问题的算法设计和实现，并将实现结果与现有的参考文献进行比较，验证算法的正确性和优越性。
2.在经典SMGS问题的基础上，添加安装时间，探究不同启发式算法在该问题中的效果，比较不同算法在时间和空间效率上的差异，并进行参数调整，以达到最优解的效果。
3.分析实际生产线的数据并构造合适的模型，研究如何将理论研究应用于实际环境，扩展模型适应性。
四、预期成果
本文将取得以下成果：
1.设计并实现适用于带有安装时间的单机成组排序问题求解的启发式算法，并验证算法的有效性和优越性。
2.分析带有安装时间的单机成组排序问题与经典SMGS问题的异同，并探究如何更好地在SMGS问题中添加安装时间。
3.将理论研究应用于实际生产线中，研究如何优化生产调度问题。
四、参考文献
[1]Li,H.,Zheng,X.,&Wang,S.(2017).Single-machinegroupschedulingwithalearningeffectandjobeligibilityconsiderations.InternationalJournalofProductionResearch,55(7),2026-2045.
[2]Yuan,X.,&Cai,X.(2017).Abi-criteriaapproximationalgorithmforthesinglemachinegroupschedulingproblemwithregularcriterionandgrouptechnology.JournalofCombinatorialOptimization,34(1),20-38.
[3]Tourkani,M.R.,Gharakhani,M.,&Jolai,F.(2015).Solvingasingle-machinegroup-schedulingproblemwithdifferentsequence-dependentsetuptimesoutsidethegroupsinordertominimizingtheMakespan.TheInternationalJournalofAdvancedManufacturingTechnology,80(1-4),563-573.
[4]Zhu,K.,&Cui,X.(2017).Amemeticalgorithmforthesinglemachinegroupschedulingproblemwithsequence-dependentsetuptimes.ComputersandIndustrialEngineering,105,252-263.