No label defined (Q3767115)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4025149
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4025149 |
Statements
1987
0 references
one-machine problem
0 references
Preemptions
0 references
0.836029589176178
0 references
The one-machine problem for a job set J is considered. Preemptions are allowed at integer moments. The processing of jobs begins at some moment t. For every job i the function \(\phi_ i\) and the processing time \(p_ i\) are given. A schedule R is defined if for every unit-time inteval \([t+\nu -1\), \(t+\nu)\), \(\nu\in \{1,2,...,P\}\), \(P=\sum^{n}_{i=1}P_ i\), \(n=| J|\), the job which is being processed in this interval is defined. The objective is to minimize the functional F(t,R) for a given t, where \[ F(t,R)=F(\phi_{\lambda_ 1}(t),\phi_{\lambda_ 2}(t+1),...,\phi_{\lambda_ P}(t+P-1)),\quad \lambda_{\nu}\in \{1,2,...,P\}, \] and \(\lambda_{\nu}=i\) if the job i is processed in the interval \([t+\nu -1\), \(t+\nu)\). It is supposed that the functional F satisfies the following conditions: (1) F is a symmetrical functional, (2) \(F(x_ 1,x_ 2,...,x_ s)=F(x_ 1,F(x_ 2,...,x_ s))\), (3) F is a non-decreasing functional. It is supposed also that the functions \(\phi_ i\) satisfy some additional conditions. An earlier published algorithm for the optimal schedule construction is described. Provided, that the optimal schedule for the set J is constructed, an O(n) algorithm for the optimal schedule construction for a set J' is suggested, where \(| J'| =n\) and for some \(i^ o\), \(P_ i'=P_ i\), \(i\neq i^ o\), \(\phi_ i'=\phi_ i\), \(i=1,...,n\) and \(t'_{i^ o}=t_{i^ o}+1\) or \(t'_{i^ o}=t_{i^ o}-1\).
0 references