scientific article; zbMATH DE number 4025149

From MaRDI portal
Publication:3767115





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\).











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3767115)