Hybridization of harmony search with variable neighborhood search for restrictive single-machine earliness/tardiness problem
Hybridization of harmony search with variable neighborhood search for restrictive single-machine earliness/tardiness problem
复制标题
和谐搜索与可变邻域搜索的混合解决限制性单机提前/迟到问题
DOI：
10.1016/j.ins.2012.11.007
复制
发表时间：
2013-03-20
影响因子：
8.1
通讯作者：
Zhou, Hong
中科院分区：
文献类型：
--
作者：
Liu, Le;Zhou, Hong
提前/拖期调度，与准时制生产理念，是至关重要的，在降低生产成本，同时保持高的服务水平。在这篇文章中，著名的限制性单机提前/拖期调度问题（RSMETP）的解决。一种新的混合元启发式，命名为PHVNS，开发这个NP-难问题。在拟议的PHVNS中有三个主要创新方面。首先，基于置换和声搜索（PHS）的RSMETP的特点和最优性的规定。其次，为了提供一个有效的平衡之间的全球多样化和局部集约化，增强的基本可变邻域搜索（EBVNS）被纳入迭代PHS。第三，几个问题相关的机制，以促进PHVNS的搜索过程中，如独特的时间表表示，具体的调整和加速的新和谐向量，和本地搜索策略在一个邻域内。在PHVNS的主要参数进行了广泛的校准与精心设计的实验的帮助下。为了评估和验证微调PHVNS，计算实验进行了测试套件的280个基准实例。结果表明，在大多数情况下，经过调整的PHVNS能够在合理的时间内达到高质量的解决方案。与一些最先进的RSMETP元算法相比，PHVNS显示出很高的竞争力。(C)2012 Elsevier Inc. All rights reserved.
Earliness/tardiness scheduling, in connection with Just-In-Time manufacturing philosophy, is crucial in reducing the production cost while maintaining a high service level. In this article, the well-known restrictive single-machine earliness/tardiness scheduling problem (RSMETP) is addressed. A novel hybrid metaheuristic, named as PHVNS, is developed for this NP-hard problem. There are three main innovative aspects in the proposed PHVNS. First, a permutation-based harmony search (PHS) is developed in compliance with the RSMETP features and optimality properties. Secondly, in order to provide an effective balance between the global diversification and local intensification, an enhanced basic variable neighborhood search (EBVNS) is incorporated into the iterative PHS. Thirdly, several problem-dependent mechanisms are introduced to facilitate the search process of PHVNS, such as the distinctive schedule representation, specific tweaks and speed-ups to the new harmony vector, and local search strategies within a neighborhood. An extensive calibration for the main parameters in PHVNS is carried out with the aid of a carefully designed set of experiments. To evaluate and validate the fine-tuned PHVNS, computational experiments are conducted upon the test suite of 280 benchmark instances. As demonstrated in the results, the tuned PHVNS is capable of reaching the high-quality solutions in reasonable time for most of the instances. Compared with some state-of-the-art metaheuristics for RSMETP, PHVNS shows high competitiveness. (C) 2012 Elsevier Inc. All rights reserved.