Online scheduling on a single machine with grouped processing times
type: Item
instance of: scholarly article
title: Online scheduling on a single machine with grouped processing times
zbMATH Open document ID: 1418.90116
DOI: 10.1155/2015/805294
author: Qijia Liu
author: Long Wan
author: Lijun Wei
published in: Discrete Dynamics in Nature and Society
publication date: 2019-02-19T00:00:00Z
review text: Summary: We consider the online scheduling problem on a single machine with the assumption that all jobs have their processing times in \([p,(1 + \alpha) p]\), where \(p > 0\) and \(\alpha = (\sqrt{5} - 1) / 2\). All jobs arrive over time, and each job and its processing time become known at its arrival time. The jobs should be first processed on a single machine and then delivered by a vehicle to some customer. When the capacity of the vehicle is infinite, we provide an online algorithm with the best competitive ratio of \((\sqrt{5} + 1) / 2\). When the capacity of the vehicle is finite, that is, the vehicle can deliver at most \(c\) jobs at a time, we provide another best possible online algorithm with the competitive ratio of \((\sqrt{5} + 1) / 2\).
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68W27
zbMATH DE Number: 7025501
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2015/805294
OpenAlex ID: W2021231597
Wikidata QID: Q59105465
cites work: Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
cites work: Machine scheduling with job delivery coordination
cites work: Integrated Scheduling of Production and Distribution Operations
cites work: Supply Chain Scheduling: Batching and Delivery
cites work: Machine scheduling with transportation considerations
cites work: On the machine scheduling problem with job delivery coordination
cites work: Q4821818
cites work: A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
cites work: Restarts can help in the on-line minimization of the maximum delivery time on a single machine
cites work: On-line integrated production-distribution scheduling problems with capacitated deliveries
cites work: A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times
cites work: An on-line algorithm for the single machine unbounded parallel-batching scheduling with large delivery times
cites work: An optimal online algorithm for single machine scheduling with bounded delivery times
cites work: Optimal algorithms for online single machine scheduling with deteriorating jobs
cites work: Parallel machine scheduling of machine-dependent jobs with unit-length.
cites work: Online batch scheduling of equal-length jobs on two identical batch machines to maximise the number of early jobs
cites work: Online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead
cites work: Optimal on-line algorithms for one batch machine with grouped processing times
cites work: On-line integrated production and outbound distribution scheduling to minimize the maximum delivery completion time
Recommended article: Optimal on-line algorithms for one batch machine with grouped processing times
Recommended article: Online Single Machine Batch Scheduling
Recommended article: Single-machine online scheduling of jobs with non-delayed processing constraint
Recommended article: On-line scheduling on a single machine: Minimizing the total completion time
Recommended article: Online scheduling of jobs with kind release times and deadlines on a single machine
Recommended article: Online scheduling with equal processing times and machine eligibility constraints
Recommended article: Single machine group scheduling with time and position dependent processing times
Recommended article: Q4835595
Recommended article: Q5234776
Recommended article: Q3461600
description: scientific article; zbMATH DE number 7025501