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 68
- Downloads 0
A Distributed Decision-Support System for Virtual Prototyping
Virtual Prototyping (VP) is a data-driven design process that promotes both knowledge reuse and innovation. High-profile applications in the automotive and aerospace industries have demonstrated its potential to signific...
Three-Machine Flowshop Scheduling Problem to Minimize Total Completion Time with Bounded Setup and Processing Times
The three-machine flowshop scheduling problem to minimize total completion time is studied where setup times are treated as separate from processing times. Setup and processing times of all jobs on all machines are unkno...
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...
Analogous Forecasting of Products with a Short Life Cycle
Managing a supply chain for products with a short life cycle, like fashion apparel, high-tech, personal computers, toys, CD’s etc., is challenging for many companies (Fisher and Raman, 1999). Because the life cycles of t...
Resource Management in Machine Scheduling Problems: A Survey
The paper is a survey devoted to job scheduling problems with resource allocation. We present the results available in the scientific literature for commonly used models of job processing times and job release dates, i.e...