Online citations, reference lists, and bibliographies.
← Back to Search

Single Machine Scheduling With Chain: Structured Precedence Constraints And Separation Time Windows

C. Chu, J. Proth
Published 1996 · Computer Science

Save to my Library
Download PDF
Analyze on Scholarcy Visualize in Litmaps
Share
Reduce the time it takes to create your bibliography by a factor of 10 by using the world’s favourite reference manager
Time to take this seriously.
Get Citationsy
We consider a single machine scheduling problem which we studied to improve the efficiency of an automated medical laboratory. In this problem, there are not only chain structured precedence constraints, but also minimal and maximal times separating successive jobs in the same chain (separation time windows). The criterion to be minimized is the makespan. Potential applications are not restricted to medical analysis. This problem often arises in systems where chemical processes are involved. Therefore the problem studied in this paper is important in practice. We prove that the problem is nonpolynomial (NP)-complete. As a consequence, we propose three heuristics for large size problems and a branch and bound based algorithm for small size problems. Computational results are reported.
This paper references
10.1080/05695557208974852
The One-Machine Sequencing Problem with Early Starts and Due Dates
M. I. Dessouky (1972)
10.1002/NAV.3800200106
On sequencing with earliest starts and due dates with application to computing bounds for the (n/m/G/Fmax) problem
P. Bratley (1973)
10.1002/NAV.3800210112
Sequencing with due-dates and early start times to minimize maximum tardiness
K. Baker (1974)
10.1111/J.1467-9574.1976.TB00264.X
Minimizing maximum lateness on one machine : Computational experience and some applications
B. Lageweg (1975)
10.1287/opre.23.3.475
On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness
Graham McMahon (1975)
10.1080/05695557608975070
Mathematical Programming Solution of a Hoist Scheduling Program
L. Phillips (1976)
10.1080/07408178508975300
A Forward-Backward Procedure for the Single Machine Problem to Minimize Maximum Lateness
R. E. Larson (1980)
10.1016/0377-2217(86)90247-X
A note on minimizing maximum lateness in a one-machine sequencing problem with release dates
E. Nowicki (1986)
10.1016/0377-2217(86)90190-6
Average and worst-case analysis of heuristics for the maximum tardiness problem
N. Hall (1986)
10.1016/0377-2217(86)90191-8
A block approach for single-machine scheduling with release dates and due dates
J. Grabowski (1986)
10.1016/0305-0483(87)90071-5
Single machine scheduling research
Sushil K. Gupta (1987)
10.1080/07408178808966165
Hoist Scheduling For A PCB Electroplating Facility
G. Shapiro (1988)
Sequencing and scheduling: algorithms and complexity
E. Lawler (1989)
10.1287/opre.38.4.624
Efficient Shortest Path Simplex Algorithms
D. Goldfarb (1990)
10.1287/MNSC.37.12.1629
The minimum common-cycle algorithm for cyclic scheduling of two material handling hoists with time window constraints
L. Lei (1991)
10.1109/ICSMC.1992.271589
Improving the time resolution of schedules generated via Lagrangian relaxation algorithms
T. Owens (1992)
10.1016/0360-8352(93)90264-X
The one-machine sequencing problem with dependent jobs
S. Dauzère-Pérès (1993)
10.1109/9.231461
Scheduling of manufacturing systems using the Lagrangian relaxation technique
P. Luh (1993)
Graphes et algorithmes
M. Gondran (1995)
10.1109/70.660860
Cyclic scheduling of a hoist with time window constraints
H. Chen (1998)



This paper is referenced by
10.1007/s10951-021-00683-w
A hybrid evolutionary approach to job-shop scheduling with generic time lags
Madiha Harrabi (2021)
10.1016/j.ejor.2019.08.045
Coupled task scheduling with exact delays: Literature review and models
M. Khatami (2020)
10.1016/J.CIE.2019.07.048
Minimizing the makespan in a flow shop environment under minimum and maximum time-lag constraints
Hamed Samarghandi (2019)
10.1007/s40092-019-00331-1
MILP models and valid inequalities for the two-machine permutation flowshop scheduling problem with minimal time lags
Imen Hamdi (2019)
10.1109/CoDIT.2018.8394918
Max-plus to solve the cyclic job shop problem with time lags
J. Barman (2018)
10.2139/ssrn.3333563
Coupled Task Scheduling With Exact Delays: Literature Review and Models
M. Khatami (2018)
10.1007/s10479-018-2775-5
Non-permutation flowshop scheduling problem with minimal and maximal time lags: theoretical study and heuristic
Emna Dhouib (2018)
10.1016/j.cie.2017.08.024
Efficient heuristic for solving non-permutation flow-shop scheduling problems with maximal and minimal time lags
Song Ye (2017)
10.1007/S10033-017-0108-2
Effective Iterated Greedy Algorithm for Flow-Shop Scheduling Problems with Time lags
Ning Zhao (2017)
10.1080/0305215X.2015.1099639
Minimizing the total completion time in a two-machine flowshop problem with time delays
Mohamed Kais Msakni (2016)
10.1016/j.cor.2015.10.006
An efficient new heuristic for the hoist scheduling problem
A. E. Amraoui (2016)
10.1007/s11590-014-0761-7
Upper and lower bounds for the permutation flowshop scheduling problem with minimal time lags
Imen Hamdi (2015)
10.1007/s12351-014-0166-5
Minimizing total tardiness in the permutation flowshop scheduling problem with minimal and maximal time lags
Imen Hamdi (2015)
10.1109/CoDIT.2014.6996865
Lagrangian relaxation for the permutation flowshop scheduling problem with minimal and maximal time lags
Imen Hamdi (2014)
10.1002/9781118731598.CH4
A Comparison of Local Search Metaheuristics for a Hierarchical Flow Shop Optimization Problem with Time Lags
Emna Dhouib (2013)
10.3182/20121003-3-MX-4033.00014
Using max-plus to solve the job shop problem with time lags
J. Cury (2012)
10.1057/jors.2010.120
Scheduling jobs with chain precedence constraints and deteriorating jobs
J.-B. Wang (2011)
10.4028/www.scientific.net/AMM.44-47.3692
An Equilibrium Principle on the AON Network for Single-Machine Scheduling Problem with Time Lags
C. Y. Yu (2010)
10.1109/CCDC.2009.5191609
Neighborhood search algorithm for one-machine scheduling problem with time lags
Zhao Rui-guo (2009)
Contribution à l'étude des problèmes d'ordonnancement flowshop avec contraintes supplémentaires : Complexité et méthodes de résolution
A. Oulamara (2009)
10.1080/00207540802320164
Permutation flow shops with exact time lags to minimise maximum lateness
Julien Fondrevelle (2009)
10.1109/CCDC.2009.5192354
Single-machine scheduling problem in plate hot rolling production
Yu Chun-yue (2009)
10.1016/J.IJPE.2006.08.018
Permutation flowshop scheduling problems with time lags to minimize the weighted sum of machine completion times
Julien Fondrevelle (2008)
10.1007/s10951-006-8501-1
A faster polynomial algorithm for 2-cyclic robotic scheduling
C. Chu (2006)
10.1016/J.IJPE.2004.12.008
Scheduling issues for environmentally responsible manufacturing: The case of hoist scheduling in an electroplating line
Corinne Subaï (2006)
10.1016/j.cor.2004.11.006
Permutation flowshop scheduling problems with maximal and minimal time lags
Julien Fondrevelle (2006)
10.1016/J.RCIM.2003.10.003
Minimum makespan task sequencing with multiple shared resources
M. Caramia (2004)
10.1109/70.988976
Multicyclic hoist scheduling with constant processing times
A. Che (2002)
10.1016/S0360-8352(00)00048-6
Minimizing the sum of earliness/tardiness in multi-machine scheduling: a mixed integer programming approach
Zhiwei Zhu (2000)
10.1023/A:1018995317468
Cyclic scheduling in robotic flowshops
Y. Crama (2000)
10.1109/70.850639
Applying a component-based software architecture to robotic workcell applications
James E. Beck (2000)
10.1007/978-1-4471-0855-9_3
Single and Multi-Machine Scheduling of Jobs in Production Systems
B. Frankovic (1999)
See more
Semantic Scholar Logo Some data provided by SemanticScholar