CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

A note on the complexity of flow-shop scheduling with deteriorating jobs

Karin Thörnblad (Institutionen för matematiska vetenskaper) ; Michael Patriksson (Institutionen för matematiska vetenskaper, matematik)
Discrete Applied Mathematics (0166-218X). Vol. 159 (2011), 4, p. 251-253.
[Artikel, refereegranskad vetenskaplig]

This paper is a note on “Complexity analysis of job-shop scheduling with deteriorating jobs” [G. Mosheiov, Complexity analysis of job-shop scheduling with deteriorating jobs, Discrete Applied Mathematics 117 (2002) 195–209]. A proportional deterioration rate is assumed and the objective is the minimization of the makespan. Mosheiov presents NP-hardness results for flow-shops and open-shops with three or more machines and for job-shops with two or more machines. The proof of NP-hardness for the flow-shop case is however not correct. This paper provides a correct proof.

Nyckelord: Deteriorating jobs, Flow shop, Makespan, NP-hardness


The article was accepted for publication on 9 November 2010, and is available online since 4 December 2010.



Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2010-12-07. Senast ändrad 2016-07-19.
CPL Pubid: 130128

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för matematiska vetenskaperInstitutionen för matematiska vetenskaper (GU)
Institutionen för matematiska vetenskaper, matematik (2005-2016)

Ämnesområden

Produktion
Transport
Tillämpad matematik
Optimeringslära, systemteori

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:


On the Optimization of Schedules of a Multitask Production Cell


Mathematical Optimization in Flexible Job Shop Scheduling: Modelling, Analysis, and Case Studies