License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.55
URN: urn:nbn:de:0030-drops-68236
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6823/
Go to the corresponding LIPIcs Volume Portal

Luo, Wenchang ; Xu, Yao ; Tong, Weitian ; Lin, Guohui

Single Machine Scheduling with Job-Dependent Machine Deterioration

pdf-format:
LIPIcs-ISAAC-2016-55.pdf (0.5 MB)

Abstract

We consider the single machine scheduling problem with job-dependent machine deterioration. In the problem, we are given a single machine with an initial non-negative maintenance level, and a set of jobs each with a non-preemptive processing time and a machine deterioration. Such a machine deterioration quantifies the decrement in the machine maintenance level after processing the job. To avoid machine breakdown, one should guarantee a non-negative maintenance level at any time point; and whenever necessary, a maintenance activity must be allocated for restoring the machine maintenance level. The goal of the problem is to schedule the jobs and the maintenance activities such that the total completion time of jobs is minimized. There are two variants of maintenance activities: in the partial maintenance case each activity can be allocated to increase the machine maintenance level to any level not exceeding the maximum; in the full maintenance case every activity must be allocated to increase the machine maintenance level to the maximum. In a recent work, the problem in the full maintenance case has been proven NP-hard; several special cases of the problem in the partial maintenance case were shown solvable in polynomial time, but the complexity of the general problem is left open. In this paper we first prove that the problem in the partial maintenance case is NP-hard, thus settling the open problem; we then design a 2-approximation algorithm.

BibTeX - Entry

@InProceedings{luo_et_al:LIPIcs:2016:6823,
  author =	{Wenchang Luo and Yao Xu and Weitian Tong and Guohui Lin},
  title =	{{Single Machine Scheduling with Job-Dependent Machine Deterioration}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6823},
  URN =		{urn:nbn:de:0030-drops-68236},
  doi =		{10.4230/LIPIcs.ISAAC.2016.55},
  annote =	{Keywords: Scheduling, machine deterioration, maintenance, NP-hard, approxima- tion algorithm}
}

Keywords: Scheduling, machine deterioration, maintenance, NP-hard, approxima- tion algorithm
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI