Single Bounded Parallel-Batch Machine Scheduling with an Unavailability Constraint and Job Delivery

Jing Fan, C. T. Ng, T. C.E. Cheng, Hui Shi

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)

Abstract

We consider a scheduling problem where a manufacturer processes a set of jobs for a customer and delivers the completed jobs to the customer. The job sizes and processing times are given. The objective is to minimize the maximum delivery time to the customer. In the production stage, one machine with an unavailability period is used to process the jobs. The machine has a fixed capacity and the jobs are processed in batches under the condition that the total size of the jobs in a batch cannot exceed the machine capacity. The processing time of a batch is the maximum processing time of the jobs contained in the batch. In addition, each batch is non-resumable, i.e., if the processing of a batch cannot be completed before the unavailability period, the batch needs to be processed anew after the unavailability interval. In the distribution stage, the manufacturer assigns a vehicle with a fixed capacity to deliver the completed jobs. The total size of the completed jobs in one delivery cannot exceed the vehicle capacity. We first consider the case where the jobs have the same size and arbitrary processing times, for which we provide a 3/2-approximation algorithm and show that the worst-case ratio is tight. We then consider the case where the jobs have the same processing time and arbitrary sizes, for which we provide a 5/3-approximation algorithm and show that the worst-case ratio is tight.

Original languageEnglish
Title of host publicationAlgorithmic Aspects in Information and Management - 14th International Conference, AAIM 2020, Proceedings
EditorsZhao Zhang, Wei Li, Ding-Zhu Du
PublisherSpringer
Pages525-536
Number of pages12
ISBN (Print)9783030576011
DOIs
Publication statusPublished - Aug 2020
Event14th International Conference on Algorithmic Aspects in Information and Management, AAIM 2020 - Jinhua, China
Duration: 10 Aug 202012 Aug 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12290 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Algorithmic Aspects in Information and Management, AAIM 2020
Country/TerritoryChina
CityJinhua
Period10/08/2012/08/20

Keywords

  • Approximation algorithm
  • Parallel-batch
  • Production and delivery
  • Unavailability constraint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this