UnivTrevesV1, Istex, Corpus, bibRecord, 000A56

An approximation algorithm for the license and shift class design problem

Identifieur interne : 000A56 ( Istex/Corpus ); précédent : 000A55; suivant : 000A57

An approximation algorithm for the license and shift class design problem

Source :

European Journal of Operational Research [ 0377-2217 ] ; 1994.

RBID : ISTEX:EBE7F352AA0F3F19566DC20EA93D526F5DE33F5C

Abstract

In this paper a generalization of the license and shift class design problem is considered. Let J be a set of jobs which have to be carried out in specified time intervals, let E be a set of different engineer licenses and Z be a set of shifts. Given a price P(e, z) ϵ ∈+ for engineers with license e ϵ E assigned to shift z ϵ Z, the problem is to find numbers of engineers to carry out all jobs with minimum cost. An approximation algorithm with time complexity O(|E|·|Z|·|J|2) and approximation bound O(log|J|) is proposed for this problem.

Url:

https://api.istex.fr/document/EBE7F352AA0F3F19566DC20EA93D526F5DE33F5C/fulltext/pdf

DOI: 10.1016/0377-2217(94)90150-3

Links to Exploration step

ISTEX:EBE7F352AA0F3F19566DC20EA93D526F5DE33F5C

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>An approximation algorithm for the license and shift class design problem</title>
<author><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name>
<affiliation><mods:affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, 54286 Trier, Germany</mods:affiliation>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:EBE7F352AA0F3F19566DC20EA93D526F5DE33F5C</idno>
<date when="1994" year="1994">1994</date>
<idno type="doi">10.1016/0377-2217(94)90150-3</idno>
<idno type="url">https://api.istex.fr/document/EBE7F352AA0F3F19566DC20EA93D526F5DE33F5C/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000A56</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000A56</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a">An approximation algorithm for the license and shift class design problem</title>
<author><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name>
<affiliation><mods:affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, 54286 Trier, Germany</mods:affiliation>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">European Journal of Operational Research</title>
<title level="j" type="abbrev">EOR</title>
<idno type="ISSN">0377-2217</idno>
<imprint><publisher>ELSEVIER</publisher>
<date type="published" when="1994">1994</date>
<biblScope unit="volume">73</biblScope>
<biblScope unit="issue">1</biblScope>
<biblScope unit="page" from="127">127</biblScope>
<biblScope unit="page" to="131">131</biblScope>
</imprint>
<idno type="ISSN">0377-2217</idno>
</series>
<idno type="istex">EBE7F352AA0F3F19566DC20EA93D526F5DE33F5C</idno>
<idno type="DOI">10.1016/0377-2217(94)90150-3</idno>
<idno type="PII">0377-2217(94)90150-3</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0377-2217</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">In this paper a generalization of the license and shift class design problem is considered. Let J be a set of jobs which have to be carried out in specified time intervals, let E be a set of different engineer licenses and Z be a set of shifts. Given a price P(e, z) ϵ ∈+ for engineers with license e ϵ E assigned to shift z ϵ Z, the problem is to find numbers of engineers to carry out all jobs with minimum cost. An approximation algorithm with time complexity O(|E|·|Z|·|J|2) and approximation bound O(log|J|) is proposed for this problem.</div>
</front>
</TEI>
<istex><corpusName>elsevier</corpusName>
<author><json:item><name>Klaus Jansen</name>
<affiliations><json:string>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, 54286 Trier, Germany</json:string>
</affiliations>
</json:item>
</author>
<subject><json:item><lang><json:string>eng</json:string>
</lang>
<value>Design planning</value>
</json:item>
<json:item><lang><json:string>eng</json:string>
</lang>
<value>Scheduling</value>
</json:item>
<json:item><lang><json:string>eng</json:string>
</lang>
<value>Graphs</value>
</json:item>
<json:item><lang><json:string>eng</json:string>
</lang>
<value>Heuristics</value>
</json:item>
</subject>
<language><json:string>eng</json:string>
</language>
<originalGenre><json:string>Full-length article</json:string>
</originalGenre>
<abstract>In this paper a generalization of the license and shift class design problem is considered. Let J be a set of jobs which have to be carried out in specified time intervals, let E be a set of different engineer licenses and Z be a set of shifts. Given a price P(e, z) ϵ ∈+ for engineers with license e ϵ E assigned to shift z ϵ Z, the problem is to find numbers of engineers to carry out all jobs with minimum cost. An approximation algorithm with time complexity O(|E|·|Z|·|J|2) and approximation bound O(log|J|) is proposed for this problem.</abstract>
<qualityIndicators><score>4.275</score>
<pdfVersion>1.2</pdfVersion>
<pdfPageSize>548 x 756 pts</pdfPageSize>
<refBibsNative>true</refBibsNative>
<keywordCount>4</keywordCount>
<abstractCharCount>542</abstractCharCount>
<pdfWordCount>3075</pdfWordCount>
<pdfCharCount>14245</pdfCharCount>
<pdfPageCount>5</pdfPageCount>
<abstractWordCount>100</abstractWordCount>
</qualityIndicators>
<title>An approximation algorithm for the license and shift class design problem</title>
<pii><json:string>0377-2217(94)90150-3</json:string>
</pii>
<refBibs><json:item><author><json:item><name>V. Chvatal</name>
</json:item>
</author>
<host><volume>4</volume>
<pages><last>235</last>
<first>233</first>
</pages>
<author></author>
<title>Mathematics of Operations Research</title>
</host>
<title>A greedy heuristic for the set covering problem</title>
</json:item>
<json:item><author><json:item><name>G.L. Dantzig</name>
</json:item>
<json:item><name>D.R. Fulkerson</name>
</json:item>
</author>
<host><volume>1</volume>
<pages><last>222</last>
<first>217</first>
</pages>
<author></author>
<title>Naval Research Logistics Quarterly</title>
</host>
<title>Minimizing the number of tankers to meet a fixed schedule</title>
</json:item>
<json:item><author><json:item><name>V.R. Doneti</name>
</json:item>
<json:item><name>H. Emmons</name>
</json:item>
</author>
<host><volume>40</volume>
<pages><last>85</last>
<first>76</first>
</pages>
<issue>Suppl. 1</issue>
<author></author>
<title>Operations Research</title>
</host>
<title>Interval scheduling with processors of two types</title>
</json:item>
<json:item><author><json:item><name>I. Gertsbakh</name>
</json:item>
<json:item><name>H.I. Stern</name>
</json:item>
</author>
<host><volume>26</volume>
<pages><last>85</last>
<first>68</first>
</pages>
<author></author>
<title>Operations Research</title>
</host>
<title>Minimal resources for fixed and variable job schedules</title>
</json:item>
<json:item><author><json:item><name>U.I. Gupta</name>
</json:item>
<json:item><name>D.T. Lee</name>
</json:item>
<json:item><name>J.Y.-T. Leung</name>
</json:item>
</author>
<host><volume>28</volume>
<pages><last>810</last>
<first>807</first>
</pages>
<author></author>
<title>IEEE Transactions on Computers</title>
</host>
<title>An optimal solution to the channel assignment problem</title>
</json:item>
<json:item><author><json:item><name>U.I. Gupta</name>
</json:item>
<json:item><name>D.T. Lee</name>
</json:item>
<json:item><name>J.Y.-T. Leung</name>
</json:item>
</author>
<host><volume>12</volume>
<pages><last>467</last>
<first>459</first>
</pages>
<author></author>
<title>Networks</title>
</host>
<title>Efficient algorithms for interval graphs and circular arc graphs</title>
</json:item>
<json:item><author><json:item><name>K. Jansen</name>
</json:item>
</author>
<host><volume>104</volume>
<pages><last>298</last>
<first>285</first>
</pages>
<author></author>
<title>Theoretical Computer Science</title>
</host>
<title>Processor-optimization for flow graphs</title>
</json:item>
<json:item><author><json:item><name>R.M. Karp</name>
</json:item>
</author>
<host><pages><last>104</last>
<first>85</first>
</pages>
<author></author>
<title>Complexity of Computer Computations</title>
</host>
<title>Reducibility among combinatorial problems</title>
</json:item>
<json:item><host><author></author>
</host>
</json:item>
<json:item><author><json:item><name>A.W.J. Kolen</name>
</json:item>
<json:item><name>L.G. Kroon</name>
</json:item>
</author>
<host><volume>54</volume>
<pages><last>38</last>
<first>23</first>
</pages>
<author></author>
<title>European Journal of Operational Research</title>
</host>
<title>On the computational complexity of (maximum) class scheduling</title>
</json:item>
<json:item><author><json:item><name>L.G. Kroon</name>
</json:item>
</author>
<host><author></author>
<title>Thesis</title>
</host>
<serie><author></author>
<title>Thesis</title>
</serie>
<title>Job scheduling and capacity planning in aircraft maintance</title>
</json:item>
</refBibs>
<genre><json:string>research-article</json:string>
</genre>
<serie><language><json:string>unknown</json:string>
</language>
<title>Thesis</title>
</serie>
<host><volume>73</volume>
<pii><json:string>S0377-2217(00)X0391-8</json:string>
</pii>
<pages><last>131</last>
<first>127</first>
</pages>
<issn><json:string>0377-2217</json:string>
</issn>
<issue>1</issue>
<genre><json:string>journal</json:string>
</genre>
<language><json:string>unknown</json:string>
</language>
<title>European Journal of Operational Research</title>
<publicationDate>1994</publicationDate>
</host>
<categories><wos><json:string>science</json:string>
<json:string>operations research & management science</json:string>
</wos>
<scienceMetrix><json:string>applied sciences</json:string>
<json:string>engineering</json:string>
<json:string>operations research</json:string>
</scienceMetrix>
</categories>
<publicationDate>1994</publicationDate>
<copyrightDate>1994</copyrightDate>
<doi><json:string>10.1016/0377-2217(94)90150-3</json:string>
</doi>
<id>EBE7F352AA0F3F19566DC20EA93D526F5DE33F5C</id>
<score>0.7950529</score>
<fulltext><json:item><extension>pdf</extension>
<original>true</original>
<mimetype>application/pdf</mimetype>
<uri>https://api.istex.fr/document/EBE7F352AA0F3F19566DC20EA93D526F5DE33F5C/fulltext/pdf</uri>
</json:item>
<json:item><extension>zip</extension>
<original>false</original>
<mimetype>application/zip</mimetype>
<uri>https://api.istex.fr/document/EBE7F352AA0F3F19566DC20EA93D526F5DE33F5C/fulltext/zip</uri>
</json:item>
<istex:fulltextTEI uri="https://api.istex.fr/document/EBE7F352AA0F3F19566DC20EA93D526F5DE33F5C/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">An approximation algorithm for the license and shift class design problem</title>
</titleStmt>
<publicationStmt><authority>ISTEX</authority>
<publisher>ELSEVIER</publisher>
<availability><p>ELSEVIER</p>
</availability>
<date>1994</date>
</publicationStmt>
<notesStmt><note type="content">Section title: Theory and methodology</note>
</notesStmt>
<sourceDesc><biblStruct type="inbook"><analytic><title level="a">An approximation algorithm for the license and shift class design problem</title>
<author xml:id="author-1"><persName><forename type="first">Klaus</forename>
<surname>Jansen</surname>
</persName>
<note type="correspondence"><p>Correspondence to: Dr. K. Jansen, Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, 54286 Trier, Germany.</p>
</note>
<affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, 54286 Trier, Germany</affiliation>
</author>
</analytic>
<monogr><title level="j">European Journal of Operational Research</title>
<title level="j" type="abbrev">EOR</title>
<idno type="pISSN">0377-2217</idno>
<idno type="PII">S0377-2217(00)X0391-8</idno>
<imprint><publisher>ELSEVIER</publisher>
<date type="published" when="1994"></date>
<biblScope unit="volume">73</biblScope>
<biblScope unit="issue">1</biblScope>
<biblScope unit="page" from="127">127</biblScope>
<biblScope unit="page" to="131">131</biblScope>
</imprint>
</monogr>
<idno type="istex">EBE7F352AA0F3F19566DC20EA93D526F5DE33F5C</idno>
<idno type="DOI">10.1016/0377-2217(94)90150-3</idno>
<idno type="PII">0377-2217(94)90150-3</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><creation><date>1994</date>
</creation>
<langUsage><language ident="en">en</language>
</langUsage>
<abstract xml:lang="en"><p>In this paper a generalization of the license and shift class design problem is considered. Let J be a set of jobs which have to be carried out in specified time intervals, let E be a set of different engineer licenses and Z be a set of shifts. Given a price P(e, z) ϵ ∈+ for engineers with license e ϵ E assigned to shift z ϵ Z, the problem is to find numbers of engineers to carry out all jobs with minimum cost. An approximation algorithm with time complexity O(|E|·|Z|·|J|2) and approximation bound O(log|J|) is proposed for this problem.</p>
</abstract>
<textClass><keywords scheme="keyword"><list><head>Keywords</head>
<item><term>Design planning</term>
</item>
<item><term>Scheduling</term>
</item>
<item><term>Graphs</term>
</item>
<item><term>Heuristics</term>
</item>
</list>
</keywords>
</textClass>
</profileDesc>
<revisionDesc><change when="1994">Published</change>
</revisionDesc>
</teiHeader>
</istex:fulltextTEI>
<json:item><extension>txt</extension>
<original>false</original>
<mimetype>text/plain</mimetype>
<uri>https://api.istex.fr/document/EBE7F352AA0F3F19566DC20EA93D526F5DE33F5C/fulltext/txt</uri>
</json:item>
</fulltext>
<metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration>
<istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType>
<istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>EOR</jid>
<aid>94901503</aid>
<ce:pii>0377-2217(94)90150-3</ce:pii>
<ce:doi>10.1016/0377-2217(94)90150-3</ce:doi>
<ce:copyright type="unknown" year="1994"></ce:copyright>
</item-info>
<head><ce:dochead><ce:textfn>Theory and methodology</ce:textfn>
</ce:dochead>
<ce:title>An approximation algorithm for the license and shift class design problem</ce:title>
<ce:author-group><ce:author><ce:given-name>Klaus</ce:given-name>
<ce:surname>Jansen</ce:surname>
<ce:cross-ref refid="COR1"><ce:sup>∗</ce:sup>
</ce:cross-ref>
</ce:author>
<ce:affiliation><ce:textfn>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, 54286 Trier, Germany</ce:textfn>
</ce:affiliation>
<ce:correspondence id="COR1"><ce:label>∗</ce:label>
<ce:text>Correspondence to: Dr. K. Jansen, Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, 54286 Trier, Germany.</ce:text>
</ce:correspondence>
</ce:author-group>
<ce:abstract><ce:section-title>Abstract</ce:section-title>
<ce:abstract-sec><ce:simple-para>In this paper a generalization of the license and shift class design problem is considered. Let <ce:italic>J</ce:italic>
 be a set of jobs which have to be carried out in specified time intervals, let <ce:italic>E</ce:italic>
 be a set of different engineer licenses and <ce:italic>Z</ce:italic>
 be a set of shifts. Given a price <ce:italic>P</ce:italic>
(<ce:italic>e</ce:italic>
, <ce:italic>z</ce:italic>
) <ce:italic>ϵ</ce:italic>
 ∈<ce:sup>+</ce:sup>
 for engineers with license <ce:italic>e</ce:italic>
 <ce:italic>ϵ</ce:italic>
 <ce:italic>E</ce:italic>
 assigned to shift <ce:italic>z</ce:italic>
 <ce:italic>ϵ</ce:italic>
 <ce:italic>Z</ce:italic>
, the problem is to find numbers of engineers to carry out all jobs with minimum cost. An approximation algorithm with time complexity O(|<ce:italic>E</ce:italic>
|·|<ce:italic>Z</ce:italic>
|·|<ce:italic>J</ce:italic>
|<ce:sup>2</ce:sup>
) and approximation bound O(log|<ce:italic>J</ce:italic>
|) is proposed for this problem.</ce:simple-para>
</ce:abstract-sec>
</ce:abstract>
<ce:keywords><ce:section-title>Keywords</ce:section-title>
<ce:keyword><ce:text>Design planning</ce:text>
</ce:keyword>
<ce:keyword><ce:text>Scheduling</ce:text>
</ce:keyword>
<ce:keyword><ce:text>Graphs</ce:text>
</ce:keyword>
<ce:keyword><ce:text>Heuristics</ce:text>
</ce:keyword>
</ce:keywords>
</head>
</converted-article>
</istex:document>
</istex:metadataXml>
<mods version="3.6"><titleInfo><title>An approximation algorithm for the license and shift class design problem</title>
</titleInfo>
<titleInfo type="alternative" contentType="CDATA"><title>An approximation algorithm for the license and shift class design problem</title>
</titleInfo>
<name type="personal"><namePart type="given">Klaus</namePart>
<namePart type="family">Jansen</namePart>
<affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, 54286 Trier, Germany</affiliation>
<description>Correspondence to: Dr. K. Jansen, Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, 54286 Trier, Germany.</description>
<role><roleTerm type="text">author</roleTerm>
</role>
</name>
<typeOfResource>text</typeOfResource>
<genre type="research-article" displayLabel="Full-length article"></genre>
<originInfo><publisher>ELSEVIER</publisher>
<dateIssued encoding="w3cdtf">1994</dateIssued>
<copyrightDate encoding="w3cdtf">1994</copyrightDate>
</originInfo>
<language><languageTerm type="code" authority="iso639-2b">eng</languageTerm>
<languageTerm type="code" authority="rfc3066">en</languageTerm>
</language>
<physicalDescription><internetMediaType>text/html</internetMediaType>
</physicalDescription>
<abstract lang="en">In this paper a generalization of the license and shift class design problem is considered. Let J be a set of jobs which have to be carried out in specified time intervals, let E be a set of different engineer licenses and Z be a set of shifts. Given a price P(e, z) ϵ ∈+ for engineers with license e ϵ E assigned to shift z ϵ Z, the problem is to find numbers of engineers to carry out all jobs with minimum cost. An approximation algorithm with time complexity O(|E|·|Z|·|J|2) and approximation bound O(log|J|) is proposed for this problem.</abstract>
<note type="content">Section title: Theory and methodology</note>
<subject><genre>Keywords</genre>
<topic>Design planning</topic>
<topic>Scheduling</topic>
<topic>Graphs</topic>
<topic>Heuristics</topic>
</subject>
<relatedItem type="host"><titleInfo><title>European Journal of Operational Research</title>
</titleInfo>
<titleInfo type="abbreviated"><title>EOR</title>
</titleInfo>
<genre type="journal">journal</genre>
<originInfo><dateIssued encoding="w3cdtf">19940224</dateIssued>
</originInfo>
<identifier type="ISSN">0377-2217</identifier>
<identifier type="PII">S0377-2217(00)X0391-8</identifier>
<part><date>19940224</date>
<detail type="volume"><number>73</number>
<caption>vol.</caption>
</detail>
<detail type="issue"><number>1</number>
<caption>no.</caption>
</detail>
<extent unit="issue pages"><start>1</start>
<end>204</end>
</extent>
<extent unit="pages"><start>127</start>
<end>131</end>
</extent>
</part>
</relatedItem>
<identifier type="istex">EBE7F352AA0F3F19566DC20EA93D526F5DE33F5C</identifier>
<identifier type="DOI">10.1016/0377-2217(94)90150-3</identifier>
<identifier type="PII">0377-2217(94)90150-3</identifier>
<recordInfo><recordContentSource>ELSEVIER</recordContentSource>
</recordInfo>
</mods>
</metadata>
</istex>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000A56 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000A56 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    Istex
   |étape=   Corpus
   |type=    RBID
   |clé=     ISTEX:EBE7F352AA0F3F19566DC20EA93D526F5DE33F5C
   |texte=   An approximation algorithm for the license and shift class design problem
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

	Serveur d'exploration sur l'Université de Trèves
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur l'Université de Trèves

An approximation algorithm for the license and shift class design problem

An approximation algorithm for the license and shift class design problem

Source :

Abstract

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri