Some Results on Shop Scheduling with S-Precedence Constraints among Job Tasks
Open Access
- 25 November 2019
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 12 (12) , 250
Abstract
We address some special cases of job shop and flow shop scheduling problems with s-precedence constraints. Unlike the classical setting, in which precedence constraints among the tasks of a job are finish–start, here the task of a job cannot start before the task preceding it has started. We give polynomial exact algorithms for the following problems: a two-machine job shop with two jobs when recirculation is allowed (i.e., jobs can visit the same machine many times), a two-machine flow shop, and an m-machine flow shop with two jobs. We also point out some special cases whose complexity status is open.Keywords
This publication has 9 references indexed in Scilit:
- Time-Indexed Formulations for the Runway Scheduling ProblemTransportation Science, 2017
- Scheduling co-operating stacking cranes with predetermined container sequencesDiscrete Applied Mathematics, 2016
- Scheduling of uniform parallel machines with s-precedence constraintsMathematical and Computer Modelling, 2011
- Scheduling with Bully Selfish JobsTheory of Computing Systems, 2011
- Parallel machine scheduling with s-precedence constraintsIIE Transactions, 2010
- Scheduling of parallel machines to minimize total completion time subject to s-precedence constraintsComputers & Operations Research, 2009
- Complexity of shop-scheduling problems with fixed number of jobs: a surveyMathematical Methods of Operations Research, 2007
- A genetic algorithm for an industrial multiprocessor flow shop scheduling problem with recirculationEuropean Journal of Operational Research, 2004
- Flow Management in Flexible Manufacturing Cells with Pipeline OperationsManagement Science, 1993