Fixed interval scheduling with third‐party machines. Issue 3 (8th August 2020)
- Record Type:
- Journal Article
- Title:
- Fixed interval scheduling with third‐party machines. Issue 3 (8th August 2020)
- Main Title:
- Fixed interval scheduling with third‐party machines
- Authors:
- Fridman, Ilia
Kovalyov, Mikhail Y.
Pesch, Erwin
Ryzhikov, Andrew - Abstract:
- Abstract: We study a problem of scheduling n jobs on machines of two types: in‐house machines and third‐party machines. Scheduling on in‐house machines incurs no additional costs, while using third‐party machines implies costs depending on their number and the time of usage. Each job has a fixed time interval for being processed which can be divided and allocated among several machines, as long as there is only one machine processing the job at any time. No machine can process more than one job at a time. Jobs can be rejected, and they are of different importance that is reflected in the weight of each job. The objective is to find a subset of the jobs and the number of third‐party machines for any period of time so that the accepted jobs can be feasibly scheduled, the total weight of the accepted jobs is maximized, and the total machine usage costs does not exceed a given upper bound. We also study a similar problem in which the objective is to maximize the total time at which at least one job is processed. Both problems are encountered in situations in which certain activities with given start and completion times have to be serviced by human operators. Examples are air traffic control and the monitoring safe vehicle unloading. Other examples are the employment of subcontractors in agriculture, construction or transportation. We will present NP‐hardness proofs, polynomial and pseudo‐polynomial optimal algorithms and an approximation algorithm for these problems and theirAbstract: We study a problem of scheduling n jobs on machines of two types: in‐house machines and third‐party machines. Scheduling on in‐house machines incurs no additional costs, while using third‐party machines implies costs depending on their number and the time of usage. Each job has a fixed time interval for being processed which can be divided and allocated among several machines, as long as there is only one machine processing the job at any time. No machine can process more than one job at a time. Jobs can be rejected, and they are of different importance that is reflected in the weight of each job. The objective is to find a subset of the jobs and the number of third‐party machines for any period of time so that the accepted jobs can be feasibly scheduled, the total weight of the accepted jobs is maximized, and the total machine usage costs does not exceed a given upper bound. We also study a similar problem in which the objective is to maximize the total time at which at least one job is processed. Both problems are encountered in situations in which certain activities with given start and completion times have to be serviced by human operators. Examples are air traffic control and the monitoring safe vehicle unloading. Other examples are the employment of subcontractors in agriculture, construction or transportation. We will present NP‐hardness proofs, polynomial and pseudo‐polynomial optimal algorithms and an approximation algorithm for these problems and their special cases. These problems admit graph‐theoretical interpretations associated with finding independent sets and a proper vertex coloring in interval graphs. … (more)
- Is Part Of:
- Networks. Volume 77:Issue 3(2021)
- Journal:
- Networks
- Issue:
- Volume 77:Issue 3(2021)
- Issue Display:
- Volume 77, Issue 3 (2021)
- Year:
- 2021
- Volume:
- 77
- Issue:
- 3
- Issue Sort Value:
- 2021-0077-0003-0000
- Page Start:
- 361
- Page End:
- 371
- Publication Date:
- 2020-08-08
- Subjects:
- fixed interval scheduling -- outsourcing -- parallel machines -- subcontracting -- interval graphs -- air traffic control
Network analysis (Planning) -- Periodicals
658.4032 - Journal URLs:
- http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1097-0037 ↗
http://onlinelibrary.wiley.com/ ↗ - DOI:
- 10.1002/net.21973 ↗
- Languages:
- English
- ISSNs:
- 0028-3045
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 6077.205000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 15978.xml