Wyniki wyszukiwania - BazTech

1

Due window assignment and scheduling on parallel machines: a FPTAS for a bottleneck criterion

Janiak A., Janiak W., Kovalyov M. Y.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2014

|

Vol. 62, nr 4

805--808

EN

A fully polynomial time approximation scheme (FPTAS) with run time 0(nm/ εm-1) is developed for a problem which combines common due window assignment and scheduling n jobs on m identical parallel machines. The problem criterion is bottleneck (min-max) such that the maximum cost, which includes job earliness, job tardiness and due window size costs, is minimized.

2

Neighbourhood properties in some single processor scheduling problem with variable efficiency and additional resources

Gorczyca M., Janiak A., Janiak W.

Decision Making in Manufacturing and Services

|

2011

|

Vol. 5, no. 1-2

5-17

EN

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.

3

Resource management in machine scheduling problems: a survey

Janiak A., Janiak W., Lichtenstein M.

Decision Making in Manufacturing and Services

|

2007

|

Vol. 1, no. 1-2

59-89

EN

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., the models in which the job processing time or the job release date is given as a linear or convex function dependent on the amount of the additional resource allotted to the job. The scheduling models with resource dependent processing times or resource dependent release dates extend the classical scheduling models to reflect more precisely scheduling problems that appear in real life. Thus, in this paper we present the computational complexity results and solution algorithms that have been developed for this kind of problems.