View in EDS

Optimal algorithms for online batch scheduling with all possible equal-processing times under periodic pulse interruptions.

Saved in:
Bibliographic Details
Title: Optimal algorithms for online batch scheduling with all possible equal-processing times under periodic pulse interruptions.
Authors: Lin, Ran1 (AUTHOR), Feng, Huiyan1 (AUTHOR), Li, Wenhua1 (AUTHOR) liwenhua@zzu.edu.cn
Source: Discrete Applied Mathematics. Jul2025, Vol. 370, p71-83. 13p.
Subjects: Production scheduling, Online algorithms, Scheduling, Machinery, Time
Abstract: We address an online scheduling problem on a batch machine to minimize the makespan. Jobs are released online over time and can be grouped into batches simultaneously with equal-processing times. This batch machine has periodic pulse interruptions, which are machine unavailable periods with negligible length. The pulse interruptions divide the scheduling horizon into periodic available intervals. A batch can be processed only within an available interval without any preemption. For all possible equal-processing times, we develop the lower bounds on competitive ratios and provide optimal online algorithms when the batch capacity is unbounded and bounded, respectively. • We study an online batch scheduling problem with periodic pulse interruptions. • We give the lower bounds for all possible equal-processing times. • We develop the optimal online algorithms for unbounded and bounded capacity. • We show the competitive ratios of the optimal online algorithms. [ABSTRACT FROM AUTHOR]
Copyright of Discrete Applied Mathematics 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: 184751508
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Optimal algorithms for online batch scheduling with all possible equal-processing times under periodic pulse interruptions.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Lin%2C+Ran%22">Lin, Ran</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Feng%2C+Huiyan%22">Feng, Huiyan</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Li%2C+Wenhua%22">Li, Wenhua</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> liwenhua@zzu.edu.cn</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Discrete+Applied+Mathematics%22">Discrete Applied Mathematics</searchLink>. Jul2025, Vol. 370, p71-83. 13p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Production+scheduling%22">Production scheduling</searchLink><br /><searchLink fieldCode="DE" term="%22Online+algorithms%22">Online algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Scheduling%22">Scheduling</searchLink><br /><searchLink fieldCode="DE" term="%22Machinery%22">Machinery</searchLink><br /><searchLink fieldCode="DE" term="%22Time%22">Time</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We address an online scheduling problem on a batch machine to minimize the makespan. Jobs are released online over time and can be grouped into batches simultaneously with equal-processing times. This batch machine has periodic pulse interruptions, which are machine unavailable periods with negligible length. The pulse interruptions divide the scheduling horizon into periodic available intervals. A batch can be processed only within an available interval without any preemption. For all possible equal-processing times, we develop the lower bounds on competitive ratios and provide optimal online algorithms when the batch capacity is unbounded and bounded, respectively. • We study an online batch scheduling problem with periodic pulse interruptions. • We give the lower bounds for all possible equal-processing times. • We develop the optimal online algorithms for unbounded and bounded capacity. • We show the competitive ratios of the optimal online algorithms. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Discrete Applied Mathematics 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=184751508
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.dam.2025.03.008
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 13
        StartPage: 71
    Subjects:
      – SubjectFull: Production scheduling
        Type: general
      – SubjectFull: Online algorithms
        Type: general
      – SubjectFull: Scheduling
        Type: general
      – SubjectFull: Machinery
        Type: general
      – SubjectFull: Time
        Type: general
    Titles:
      – TitleFull: Optimal algorithms for online batch scheduling with all possible equal-processing times under periodic pulse interruptions.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Lin, Ran
      – PersonEntity:
          Name:
            NameFull: Feng, Huiyan
      – PersonEntity:
          Name:
            NameFull: Li, Wenhua
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 31
              M: 07
              Text: Jul2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 0166218X
          Numbering:
            – Type: volume
              Value: 370
          Titles:
            – TitleFull: Discrete Applied Mathematics
              Type: main
ResultId 1