2012-04-01, English, Article, Report edition: Single machine scheduling with small operator-non-availability periods.(Report) Rapine, Christophe; Brauner, Nadia; Finke, Gerd; ...

User activity

Share to:
 
Bookmark: http://trove.nla.gov.au/version/178217927
Physical Description
  • Report
  • Magazine/​Journal article
Published
  • Springer, 2012 April
Language
  • English

Edition details

Title
  • Single machine scheduling with small operator-non-availability periods.(Report)
Also Titled
  • Single machine scheduling with small operator-non-availability periods.
Appears In
  • Journal of Scheduling, v.15, no.2, 2012 April, p.127(13) (ISSN: 1094-6136)
Author
  • Rapine, Christophe
  • Brauner, Nadia
  • Finke, Gerd
  • Lebacque, Vassilissa
Published
  • Springer, 2012 April
Physical Description
  • Report
  • Magazine/​Journal article
Subjects
Target Audience
  • Academic
Summary
  • Byline: Christophe Rapine (1), Nadia Brauner (2), Gerd Finke (2), Vassilissa Lebacque (3) Keywords: Single machine scheduling; Unavailability constraints; Forbidden start and end; Approximation algorithm Abstract: For an industrial application in the chemical industry, we were confronted with the planning of experiments, where human intervention of a chemist is required to handle the starting and termination of each of the experiments. This gives rise to a new type of scheduling problem, namely problems of finding schedules with time periods when the tasks can neither start nor finish. We consider in this paper the natural case of small periods where the duration of the periods is smaller than any processing time. This assumption corresponds to our chemical experiments lasting several days, whereas the operator unavailability periods are typically single days or week-ends. These problems are analyzed on a single machine with the makespan as criterion. We first prove that, contrary to the case of machine unavailability periods, the problem with one small operator non-availability period can be solved in polynomial time. We then derive approximation and inapproximability results for the general case of k small unavailability periods, where k may be part of the input or k may be fixed. We consider in particular the practical case of periodic and equal small unavailability periods. We prove that all these problems become NP-hard if one has kaY=​2 small unavailability periods and the problems do not allow fully polynomial time approximation schemes (FPTAS) for kaY=​3. We then analyze list scheduling algorithms and establish their performance guarantee. Author Affiliation: (1) Laboratoire LGIPM, Universite de Lorraine, ile du Saulcy, 57045, Metz Cedex 01, France (2) G-SCOP Laboratory, Grenoble University, 46 avenue Felix Viallet, Grenoble, 38031, France (3) OPTI-TIME SA, 710 Rue Aristide Berges, 38330, Montbonnot-Saint-Martin, France Article History: Registration Date: 23/​01/​2012 Online Date: 15/​02/​2012
Terms of Use
  • COPYRIGHT 2012 Springer
Language
  • English
Database
  • Gale Academic OneFile
Identifier
  • 282583604

Get this edition

Via a library membership

Library View online via
Australian Bureau of Statistics. Castles Library.
Australian College of Physical Education. Australian College of Physical Education Library.
Australian Catholic University. Alumni Access.
Australian Catholic University.
Australian Institute of Professional Education.
Australian Lutheran College. Lohe Memorial Library.
Australian School of Management. Perth Campus Library.
Avondale College. Avondale College of Higher Education Sydney Campus Library.
University of Adelaide. Barr Smith Library.
Blue Mountains International Hotel Management School.
Bond University. John and Alison Kearney Library .
Campion College Australia.
Charles Darwin University. Casuarina Campus Library.
Cengage Education.
Christian Heritage College. Christian Heritage College Library.
Deakin University. Deakin University Library.
Edith Cowan University. Edith Cowan University Library.
Australian College of Natural Medicine Pty Ltd. Endeavour College of Natural Health Library.
Excelsia College. Excelsia College Library.
Kaplan Professional. Library.
Fire & Rescue NSW. FRNSW Library.
University of Notre Dame Australia. Galvin Medical Library.
Holmesglen Institute of TAFE. Holmesglen Learning Commons.
International College of Management, Sydney. ICMS Library.
Macquarie University. Macquarie University Library.
Marcus Oldham College. Sir James Darling Resource Centre.
Melbourne Library Service.
Monash University. Monash University Library.
Moore Theological College. Moore Theological College Library.
SA Mental Health Services.
Sydney Missionary and Bible College. J.T.H. Kerr Library.
South Australian Research and Development Institute. South Australian Aquatic Sciences Centre Library.
South Western Sydney Institute of TAFE.
Swinburne University of Technology. Swinburne Library.
Tabor College Victoria.
Tabor Adelaide. Tabor College Library.
The Southport School. Senior Library.
Think: Education Group. Think Education Group Learning Resource Centre.
University of New England. Dixson Library.
University of Canberra. University of Canberra Library.
University of Wollongong. University of Wollongong Library.
University of Queensland. University of Queensland Library. UQ Library Cyberschool.
Catholic Institute of Sydney. Veech Library.
Western Sydney University. Hawkesbury Campus Library.
Show 0 more libraries...
Library View online via
Australian Bureau of Statistics. Castles Library.
University of Canberra. University of Canberra Library.
Show 0 more libraries...
Library View online via
Australian College of Physical Education. Australian College of Physical Education Library.
Australian Catholic University. Alumni Access.
Australian Catholic University.
Australian Institute of Professional Education.
Avondale College. Avondale College of Higher Education Sydney Campus Library.
Blue Mountains International Hotel Management School.
Campion College Australia.
Cengage Education.
Excelsia College. Excelsia College Library.
Kaplan Professional. Library.
Fire & Rescue NSW. FRNSW Library.
International College of Management, Sydney. ICMS Library.
Macquarie University. Macquarie University Library.
Moore Theological College. Moore Theological College Library.
Sydney Missionary and Bible College. J.T.H. Kerr Library.
South Western Sydney Institute of TAFE.
Think: Education Group. Think Education Group Learning Resource Centre.
University of New England. Dixson Library.
University of Wollongong. University of Wollongong Library.
Catholic Institute of Sydney. Veech Library.
Western Sydney University. Hawkesbury Campus Library.
Show 0 more libraries...
Library View online via
Charles Darwin University. Casuarina Campus Library.
Show 0 more libraries...
Library View online via
Bond University. John and Alison Kearney Library .
Christian Heritage College. Christian Heritage College Library.
Australian College of Natural Medicine Pty Ltd. Endeavour College of Natural Health Library.
The Southport School. Senior Library.
University of Queensland. University of Queensland Library. UQ Library Cyberschool.
Show 0 more libraries...
Library View online via
Australian Lutheran College. Lohe Memorial Library.
University of Adelaide. Barr Smith Library.
SA Mental Health Services.
South Australian Research and Development Institute. South Australian Aquatic Sciences Centre Library.
Tabor Adelaide. Tabor College Library.
Show 0 more libraries...
Library View online via
Deakin University. Deakin University Library.
Holmesglen Institute of TAFE. Holmesglen Learning Commons.
Marcus Oldham College. Sir James Darling Resource Centre.
Melbourne Library Service.
Monash University. Monash University Library.
Swinburne University of Technology. Swinburne Library.
Tabor College Victoria.
Show 0 more libraries...

Published in

Some editions of the publication "Journal of scheduling" are available from these libraries. The edition containing this article ( v.15, no.2, 2012 April, p.127(13) ) may not be available:

None of your libraries hold this item.

These 12 locations in All:

Library Access Call number(s) Formats held Language
Australian Nuclear Science and Technology Organisation. ANSTO Library. Not open to the public Held. Check with Library Periodical; Journal, magazine, other English
Charles Sturt University. CSU Library - Electronic Resources (shared). Open to the public 001228060; Full Text Available; ProQuest Central New Platform - Available from 2003. Most recent 1 year(s) not available Periodical; Journal, magazine, other English
CSIRO. Black Mountain Library. May not be open to the public 996915850001981; BP 004.413.2 Jo; Vol. 2 (1999)-v. 4 (2001) Periodical; Journal, magazine, other English
CSIRO. Library Services. Not open to the public 200231; Online access. Available for document delivery. Restrictions apply.; Vol. 1 (1998)- Periodical; Journal, magazine, other English
Edith Cowan University. Edith Cowan University Library. Open to the public Periodical; Journal, magazine, other English
Griffith University. Griffith University Library. Open to the public .b14071526; Electronic Resource : Publ. may restrict Doc. Del. Periodical; Journal, magazine, other English
Mazenod College. Mazenod College Library. Open to the public Periodical; Journal, magazine, other English
Monash Health. Not open to the public Held. Check Holdings: https://monash.on.worldcat.org Periodical; Journal, magazine, other English
Southern Cross University. University Library Lismore. Open to the public Electronic resource - Check catalogue for holdings Periodical; Journal, magazine, other English
University of Queensland. University of Queensland Library. Open to the public .b20715377; Online access via Wiley InterScience : (1998-2002). Available for document delivery - restrictions apply; Online access via SpringerLink : (2003)-. Available for document delivery - restrictions apply; Online access via ABI/Inform global at ProQuest : (2003)- except the last 365 days. Available for document delivery - restrictions apply Periodical; Journal, magazine, other English
University of Technology Sydney. University Library. Open to the public .b14005256; held Periodical; Journal, magazine, other English
Western Sydney University. Penrith Campus Library, Document Delivery. Not open to the public 9919461170001571; Online Periodical; Journal, magazine, other English
Show 0 more libraries...

This single location in Australian Capital Territory:

Library Access Call number(s) Formats held Language
CSIRO. Black Mountain Library. May not be open to the public 996915850001981; BP 004.413.2 Jo; Vol. 2 (1999)-v. 4 (2001) Periodical; Journal, magazine, other English
Show 0 more libraries...

These 5 locations in New South Wales:

Library Access Call number(s) Formats held Language
Australian Nuclear Science and Technology Organisation. ANSTO Library. Not open to the public Held. Check with Library Periodical; Journal, magazine, other English
Charles Sturt University. CSU Library - Electronic Resources (shared). Open to the public 001228060; Full Text Available; ProQuest Central New Platform - Available from 2003. Most recent 1 year(s) not available Periodical; Journal, magazine, other English
Southern Cross University. University Library Lismore. Open to the public Electronic resource - Check catalogue for holdings Periodical; Journal, magazine, other English
University of Technology Sydney. University Library. Open to the public .b14005256; held Periodical; Journal, magazine, other English
Western Sydney University. Penrith Campus Library, Document Delivery. Not open to the public 9919461170001571; Online Periodical; Journal, magazine, other English
Show 0 more libraries...
None of your libraries hold this item.

These 2 locations in Queensland:

Library Access Call number(s) Formats held Language
Griffith University. Griffith University Library. Open to the public .b14071526; Electronic Resource : Publ. may restrict Doc. Del. Periodical; Journal, magazine, other English
University of Queensland. University of Queensland Library. Open to the public .b20715377; Online access via Wiley InterScience : (1998-2002). Available for document delivery - restrictions apply; Online access via SpringerLink : (2003)-. Available for document delivery - restrictions apply; Online access via ABI/Inform global at ProQuest : (2003)- except the last 365 days. Available for document delivery - restrictions apply Periodical; Journal, magazine, other English
Show 0 more libraries...
None of your libraries hold this item.
None of your libraries hold this item.

These 3 locations in Victoria:

Library Access Call number(s) Formats held Language
CSIRO. Library Services. Not open to the public 200231; Online access. Available for document delivery. Restrictions apply.; Vol. 1 (1998)- Periodical; Journal, magazine, other English
Mazenod College. Mazenod College Library. Open to the public Periodical; Journal, magazine, other English
Monash Health. Not open to the public Held. Check Holdings: https://monash.on.worldcat.org Periodical; Journal, magazine, other English
Show 0 more libraries...
None of your libraries hold this item.

User activity


e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this edition

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this version

Add a comment