NDLI: Boundary lines between permutation flowshop problems and single machine problems

Content Provider	IEEE Xplore Digital Library
Author	Fernandez-Viagas, V. Framinan, J.M.
Copyright Year	2015
Description	Author affiliation: Sch. of Eng., Univ. of Seville, Seville, Spain (Fernandez-Viagas, V.; Framinan, J.M.)
Abstract	The permutation flowshop scheduling and the single machine scheduling problems are two classical problems in the scheduling literature. Since the former is known to be NP-hard for more than two machines, hundreds of algorithms have been implemented in the last decades to solve it. Furthermore, several computational studies have found that the permutation flowshop to minimise makespan is easily solvable for structured (i.e. processing times are job- and/or machine-correlated) instances and when the initial availability of all machines for processing jobs cannot be assumed. Our working hypothesis to explain this behaviour is that, under certain conditions of machine availability or structured processing times, only one stage in the flowshop layout determines the optimal sequence, approximately transforming the flowshop scheduling problem into a single machine scheduling problem. Since the single machine scheduling problem with makespan objective is a trivial problem where all feasible sequences are optimal, such transformation may explain why it is so easy to find good solutions for such flowshop scheduling problems. Therefore, the goal of this paper is to study under which assumptions a permutation flowshop scheduling problem can be reduced to a single machine scheduling problem. More specifically, we focus onto the two most common objectives in the literature (i.e. makespan and total flowtime). Our work is a combination of theoretical and computational analysis, therefore several properties are derived, together with an extensive computational evaluation.
Starting Page	899
Ending Page	908
File Size	710102
Page Count	10
File Format	PDF
e-ISBN	9782960053265
DOI	10.1109/IESM.2015.7380262
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-10-21
Publisher Place	Spain
Access Restriction	Subscribed
Rights Holder	International Institute for Innovation, Industrial Engineering and Entrepreneurship - I4e2
Subject Keyword	Job shop scheduling Correlation Processor scheduling Benchmark testing Minimization Single machine scheduling Signal to noise ratio
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An improved differential evolution for permutation flowshop scheduling problem with total flowtime criterion

A Discrete Electromagnetism-Like Mechanism Algorithm for Solving Distributed Permutation Flowshop Scheduling Problem

A genetic algorithm for permutation flowshop scheduling with total flowtime criterion

Solving permutation flow shop sequencing using ant colony optimization

Predictive scheduling for permutation flow shop subject to new arrival job

An evolutionary algorithm for no-wait flowshop problems with flowtime minimization

Branch and bound algorithm in optimizing job shop scheduling problems

Logic-based Benders decomposition to solve the permutation flowshop scheduling problem with time lags

Application of Node Based Coincidence algorithm for flow shop scheduling problems

Boundary lines between permutation flowshop problems and single machine problems

Similar Documents

An improved differential evolution for permutation flowshop scheduling problem with total flowtime criterion

A Discrete Electromagnetism-Like Mechanism Algorithm for Solving Distributed Permutation Flowshop Scheduling Problem

A genetic algorithm for permutation flowshop scheduling with total flowtime criterion

Solving permutation flow shop sequencing using ant colony optimization

Predictive scheduling for permutation flow shop subject to new arrival job

An evolutionary algorithm for no-wait flowshop problems with flowtime minimization

Branch and bound algorithm in optimizing job shop scheduling problems

Logic-based Benders decomposition to solve the permutation flowshop scheduling problem with time lags

Application of Node Based Coincidence algorithm for flow shop scheduling problems

Boundary lines between permutation flowshop problems and single machine problems