English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper concerns the single machine total weighted tardiness schedulingwith sequence-dependent setup times, usually referred as $1|s_{ij}|\sumw_jT_j$. In this $\mathcal{NP}$-hard problem, each job has an associatedprocessing time, due date and a weight. For each pair of jobs $i$ and $j$,there may be a setup time before starting to process $j$ in case this job isscheduled immediately after $i$. The objective is to determine a schedule thatminimizes the total weighted tardiness, where the tardiness of a job is equalto its completion time minus its due date, in case the job is completelyprocessed only after its due date, and is equal to zero otherwise. Due to itscomplexity, this problem is most commonly solved by heuristics. The aim of thiswork is to develop a simple yet effective limitation strategy that speeds upthe local search procedure without a significant loss in the solution quality.Such strategy consists of a filtering mechanism that prevents unpromising movesto be evaluated. The proposed strategy has been embedded in a local searchbased metaheuristic from the literature and tested in classical benchmarkinstances. Computational experiments revealed that the limitation strategyenabled the metaheuristic to be extremely competitive when compared to otheralgorithms from the literature, since it allowed the use of a large number ofneighborhood structures without a significant increase in the CPU time and,consequently, high quality solutions could be achieved in a matter of seconds.In addition, we analyzed the effectiveness of the proposed strategy in twoother well-known metaheuristics. Further experiments were also carried out onbenchmark instances of problem $1|s_{ij}|\sum T_j$.

Efficient local search limitation strategy for single machine total weighted tardiness scheduling with sequence-dependent setup times