Single-machine scheduling with release times, deadlines, setup times, and rejection

Single-machine scheduling where jobs have a penalty for being late or for being rejected altogether is an important (sub)problem in manufacturing, logistics, and satellite scheduling. It is known to be NP-hard in the strong sense, and there is no polynomial-time algorithm that can guarantee a constant-factor approximation (unless P=NP). We...

Tabu-Based Large Neighbourhood Search for Time/Sequence-Dependent Scheduling Problems with Time Windows

An important class of scheduling problems is characterised by time-dependency and/or sequence-dependency with time windows. We introduce and analyze four algorithmic ideas for this class: a novel hybridization of adaptive large neighbourhood search (ALNS) and tabu search (TS), randomized generic neighbourhood operators, a partial sequence...

Order Acceptance and Scheduling with Sequence-Dependent Setup Times: A New Memetic Algorithm and Benchmark of the State of the Art

The Order Acceptance and Scheduling (OAS) problem describes a class of real-world problems such as in smart manufacturing and satellite scheduling. This problem consists of simultaneously selecting a subset of orders to be processed as well as determining the associated schedule. A common generalization includes sequence-dependent setup times...

Time/Sequence-Dependent Scheduling: The design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm

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...

Tabu-Based Large Neighbourhood Search for Time-Dependent Multi-Orbit Agile Satellite Scheduling

Agile Earth observation satellite (AEOS) scheduling is complex, due to long visible time windows and time-dependent transitions between observations. We introduce a generic approach suited for scheduling problems characterised by time-dependency and/or sequence-dependency. Our approach is a novel hybridization of adaptive large neighbourhood...