الگوریتم BA-VNS ترکیبی برای زمانبندی دسته بندی ترتیبی با شغل های تخریب کننده
Abstract
1- Introduction
2- Notations and problem statement
3- The structural properties and the scheduling rule
4- The BA-VNS algorithm
5- Conclusion
References
Abstract
We study a coordinated serial-batching scheduling problem that features deteriorating jobs, financial budget, resource constraints, resource-dependent processing times, setup times, and multiple manufacturers simultaneously. A unique feature but also a significant challenge in this problem is the dual constraints on resources, i.e., financial budget and resource quantity. Some key structural properties are first identified for the setting where the jobs and resources are already assigned to each manufacturer, which enables us to develop the optimal resource allocation scheme. Then, a polynomial-time scheduling rule is proposed to search for the optimal solution for each manufacturer in this setting. Then, a hybrid BA-VNS algorithm combining Bat algorithm (BA) and variable neighborhood search (VNS) is proposed to tackle the studied problem, and the optimal scheduling rule is implemented in its encoding procedure. Finally, computational experiments are conducted to test the performance of the proposed algorithm, and the efficiency and improvements are compared with those of BA, VNS, and Particle Swarm Optimization (PSO), with respect to convergence speed as well as computational stability.
Introduction
The batch scheduling problems exist in many practical manufacturing scenarios, which constitute a significant research area in scheduling and have captured the attention of many researchers (see [1,2]). In this paper, a coordinated serial-batching scheduling problem is studied, characterized by deteriorating jobs, resource constraints, resource-dependent processing times, setup times, and multiple manufacturers simultaneously. In particular, dual resource constraints are considered, specifically, on the quantity of the actual resources and the costs of financial resources. This problem has significant practice relevance. In a typical manufacturing industry, increasing peer competition and cost pressure bring higher requirements on production efficiency. Many enterprises operate largely with resource limits, meanwhile struggling to reduce production time. In view of this, how to effectively schedule the production process under limited resources is a problem of great interests and significance. Furthermore, considering the actual production scenario, some important features, e.g., deteriorating effect and batch processing, should be taken into account. However, to the best of our knowledge, rare study has investigated this type of problems up to now. Financial constraint or financial budget is a common problem in many practical production scenarios (see, e.g., [3–7]). This set of problems considers the constraints on basically immaterial resources (i.e., money) consumed by actual non-renewable resources (e.g., fuel, materials, etc.) for processing jobs. These financial resources mainly contribute to improving managerial decisionmaking by providing more profits that can be easily calculated [8]. By extending the classical scheduling problems to the financial constraints setting, some researchers have conducted specific studies in the last decade [9,10]. On the other hand, production resource constraint is another inevitable issue that should also be considered in manufacturing process, given that resources cannot be unlimitedly increased. It should be noted here that in most cases, job processing times are related to the quantity of resources, and thus the production speed and effectiveness can be enhanced through increase in resources [11].