Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm
Open accessThe DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Abstract
In intelligent manufacturing, it is important to schedule orders from customers efficiently. Make-to-order companies may have to reject or postpone orders when the production capacity does not meet the demand. Many such real-world scheduling problems are characterised by processing times being dependent on the start time (time dependency) or on the preceding orders (sequence dependency), and typically have an earliest and latest possible start time. We introduce and analyze four algorithmic ideas for this class of time/sequence-dependent over-subscribed scheduling problems with time windows: a novel hybridization of adaptive large neighbourhood search (ALNS) and tabu search (TS), a new randomization strategy for neighbourhood operators, a partial sequence dominance heuristic, and a fast insertion strategy. Through factor analysis, we demonstrate the performance of these new algorithmic features on problem domains with varying properties. Evaluation of the resulting general purpose algorithm on three domains—an order acceptance and scheduling problem, a real-world multi-orbit agile Earth observation satellite scheduling problem, and a time-dependent orienteering problem with time windows—shows that our hybrid algorithm robustly outperforms general algorithms including a mixed integer programming method, a constraint programming method, recent state-of-the-art problem-dependent meta-heuristic methods, and a two-stage hybridization of ALNS and TS.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Selecting and scheduling observations of agile satellites
Lemaı̂tre, M., Verfaillie, G., Jouhaud, F., Lachiver, J.-M., & Bataille, N. (2002) · Aerospace Science and Technology · doi:10.1016/s1270-9638(02)01173-2 · Cited by 472 · cited 1×
“Besides, the transition time for the satellite to change its observation angle between two adjacent jobs is time/sequence-dependent (Lemaître et al. 2002).”
BackgroundLiu, X., Laporte, G., Chen, Y., & He, R. (2017) · Computers & Operations Research · doi:10.1016/j.cor.2017.04.006 · Cited by 250 · cited 14×
“Both the strategies have the same time complexity O ( n ) , but ours creates much more space in the schedule by considering postponing all the possible jobs in the solution, while Liu et al. (2017)’s method only creates limited space by moving two jobs.”
BackgroundMethodInfluentialMaximizing the value of an Earth observation satellite orbit
Cordeau, J.-F., & Laporte, G. (2005) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2601926 · Cited by 150 · cited 2×
“The first type is more common in over-subscribed problems (Bianchessi et al. 2007; Cordeau et al. 2001; Cordeau and Laporte 2005; Rogers et al. 2006; Prins et al. 2007).”
BackgroundMethod
Cited by
Song, Y., Ou, J., Pedrycz, W., Suganthan, P. N., Wang, X., Xing, L., & Zhang, Y. (2024) · IEEE Transactions on Systems, Man, and Cybernetics: Systems · doi:10.1109/tsmc.2023.3345928 · Cited by 63
Wen, Z., Li, L., Song, J., Zhang, S., & Hu, H. (2023) · Advances in Space Research · doi:10.1016/j.asr.2022.10.024 · Cited by 46
Wu, J., Song, B., Zhang, G., Ou, J., Chen, Y., Yao, F., He, L., & Xing, L. (2022) · Computers & Industrial Engineering · doi:10.1016/j.cie.2022.108823 · Cited by 44
Self-citationDRL-Based Dynamic Destroy Approaches for Agile-Satellite Mission Planning
Huang, W., Li, Z., He, X., Xiang, J., Du, X., & Liang, X. (2023) · Remote Sensing · doi:10.3390/rs15184503 · Cited by 11
A Multi-Pointer Network for Multiple Agile Optical Satellite Scheduling Problem
Liu, Z., Xiong, W., Han, C., & Zhao, K. (2024) · Aerospace · doi:10.3390/aerospace11100792 · Cited by 4
Metadata
- Authors
- He, L., de Weerdt, M., & Yorke-Smith, N.
- Venue
- Journal of Intelligent Manufacturing
- Published
- 2019-12-20
- Volume
- 31
- Issue
- 4
- Pages
- 1051-1078
- ISSN
- 0956-5515 (ISSN-L)
- 1572-8145
- OpenAlex
- W2994842245
- Cited by
- 77
- References
- 3
- FWCI
- 5.20
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm. https://app.cochat.ai/papers/10.1007/s10845-019-01518-4
- The paper
- He, L., de Weerdt, M., & Yorke-Smith, N. (2020). Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm. Journal of Intelligent Manufacturing. https://doi.org/10.1007/s10845-019-01518-4
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.