View in EDS

Best possible algorithms for online scheduling on identical batch machines with periodic pulse interruptions.

Saved in:
Bibliographic Details
Title: Best possible algorithms for online scheduling on identical batch machines with periodic pulse interruptions.
Authors: Lin, Ran1,2 (AUTHOR), Wang, Jun-Qiang1,2 (AUTHOR) wangjq@nwpu.edu.cn, Liu, Zhixin3 (AUTHOR), Xu, Jun1,2 (AUTHOR)
Source: European Journal of Operational Research. Aug2023, Vol. 309 Issue 1, p53-64. 12p.
Subjects: Online algorithms, Batch processing, Machinery, Scheduling, Production scheduling
Abstract: • Propose an online batch scheduling problem with periodic pulse interruptions. • Analyze the lower bounds on competitive ratios for the online problem. • Design the best possible online algorithms using a waiting strategy. • Prove the competitive ratios of the online algorithms. We consider an online scheduling problem on identical batch machines to minimize the makespan with periodic pulse interruptions. Periodic pulse interruptions are machine unavailable intervals with negligible length and divide the scheduling horizon into available intervals. Jobs are released online over time and processed simultaneously as batches with the same processing times on identical batch machines. Every batch must be entirely processed in an available interval without any preemption. For unbounded machine capacity, we design best possible online algorithms with the competitive ratios of 1 + η and 2 m for a single machine (m = 1) and m identical parallel machines (m ≥ 2), respectively, where η ≈ 0.8019 is the positive root of η 3 + 2 η 2 − η = 1. For bounded machine capacity, we derive a best possible online algorithm with a competitive ratio of 1 + η. [ABSTRACT FROM AUTHOR]
Copyright of European Journal of Operational Research is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 162804517
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Best possible algorithms for online scheduling on identical batch machines with periodic pulse interruptions.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Lin%2C+Ran%22">Lin, Ran</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Wang%2C+Jun-Qiang%22">Wang, Jun-Qiang</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> wangjq@nwpu.edu.cn</i><br /><searchLink fieldCode="AR" term="%22Liu%2C+Zhixin%22">Liu, Zhixin</searchLink><relatesTo>3</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Xu%2C+Jun%22">Xu, Jun</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22European+Journal+of+Operational+Research%22">European Journal of Operational Research</searchLink>. Aug2023, Vol. 309 Issue 1, p53-64. 12p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Online+algorithms%22">Online algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Batch+processing%22">Batch processing</searchLink><br /><searchLink fieldCode="DE" term="%22Machinery%22">Machinery</searchLink><br /><searchLink fieldCode="DE" term="%22Scheduling%22">Scheduling</searchLink><br /><searchLink fieldCode="DE" term="%22Production+scheduling%22">Production scheduling</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: • Propose an online batch scheduling problem with periodic pulse interruptions. • Analyze the lower bounds on competitive ratios for the online problem. • Design the best possible online algorithms using a waiting strategy. • Prove the competitive ratios of the online algorithms. We consider an online scheduling problem on identical batch machines to minimize the makespan with periodic pulse interruptions. Periodic pulse interruptions are machine unavailable intervals with negligible length and divide the scheduling horizon into available intervals. Jobs are released online over time and processed simultaneously as batches with the same processing times on identical batch machines. Every batch must be entirely processed in an available interval without any preemption. For unbounded machine capacity, we design best possible online algorithms with the competitive ratios of 1 + η and 2 m for a single machine (m = 1) and m identical parallel machines (m ≥ 2), respectively, where η ≈ 0.8019 is the positive root of η 3 + 2 η 2 − η = 1. For bounded machine capacity, we derive a best possible online algorithm with a competitive ratio of 1 + η. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of European Journal of Operational Research is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=162804517
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.ejor.2023.01.027
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 12
        StartPage: 53
    Subjects:
      – SubjectFull: Online algorithms
        Type: general
      – SubjectFull: Batch processing
        Type: general
      – SubjectFull: Machinery
        Type: general
      – SubjectFull: Scheduling
        Type: general
      – SubjectFull: Production scheduling
        Type: general
    Titles:
      – TitleFull: Best possible algorithms for online scheduling on identical batch machines with periodic pulse interruptions.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Lin, Ran
      – PersonEntity:
          Name:
            NameFull: Wang, Jun-Qiang
      – PersonEntity:
          Name:
            NameFull: Liu, Zhixin
      – PersonEntity:
          Name:
            NameFull: Xu, Jun
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 16
              M: 08
              Text: Aug2023
              Type: published
              Y: 2023
          Identifiers:
            – Type: issn-print
              Value: 03772217
          Numbering:
            – Type: volume
              Value: 309
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: European Journal of Operational Research
              Type: main
ResultId 1