Neighbourhood Properties in Some Single Processor Scheduling Problem with Variable Efficiency and Additional Resources
Journal Title: Decision Making in Manufacturing and Services - Year 2011, Vol 5, Issue 1
Abstract
In the paper, we consider a problem of scheduling a set of tasks on a single processor. Each task must be preprocessed before it can be started on a processor. The efficiency of preprocessing is variable, i.e., the rate of the task preprocessing depends on the amount of continuously divisible resource allotted to this task. This dependency is given by concave, continuous, non-negative and strictly increasing function of the resource amount. The total consumption of resource at each moment is upper bounded. The objective is to minimize the maximum task completion time. The considered problem is NP-hard. Such a problem appears, e.g., in steel mill systems, where ingots (before hot rolling on the blooming mill) have to achieve the required temperature in the preheating process in soaking pits. Some new properties of the problem are proved. These properties are used to construct the procedure for evaluation of the neighbourhood. The procedure is proposed to improve the efficiency of algorithms based on the neighbourhood concept, such as metaheuristics. The computational experiment is conducted to examine the efficiency of the proposed procedure. The described approach can be easily used in the other discrete-continuous scheduling problems.
Authors and Affiliations
Władysław Janiak, Mateusz Gorczyca, Adam Janiak
Keywords
Related Articles
- EP ID EP168382
- DOI 10.7494/dmms.2011.5.1.5
- Views 43
- Downloads 0
CP-driven Production Process Planning in Multiproject Environment
The way enterprise capabilities are used decides about its competitiveness among other ones. In that context modeling aimed at production tasks allocation planning plays a crucial role especially at concurrently executed...
Allocating Pooled Inventory According to Contributions and Entitlements
Inventory pooling, whether by centralization of stock or by mutual assistance, is known to be beneficial when demands are uncertain. But when the retailers are independent, the question is how to divide the benefits of p...
The Effect of Environmental Criteria on Locating a Biorefinery: A Green Facility Location Problem
Underestimating facility location decisions may penalize business performance over the time. Those penalties usually have been studied from the economic point of view analyzing its impact on profitability. Additionally,...
Risks and implications for decision making processes associated with existing design codes or their non-existence
Buckling phenomenon is a perplexing and unresolved issue in many safety critical structures, and it has been heavily regulated. The paper highlights the risks to decision making processes due to growing tendencies of eli...
Application of Fuzzy Based VIKOR Approach for Multi-Attribute Group Decision Making (MAGDM): A Case Study in Supplier Selection
In today’s competitive global markets, selection of a potential supplier plays an important role to cut production costs as well as material costs of the company. This leads to successful survival and sustainability in a...