Self-adaptive large neighborhood search algorithm for parallel machine scheduling problems

A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems＇ another feature lies in oversubscription, namely not all jobs can be scheduled within specified scheduling horizons due to the limited machine capacity. The objective is thus to maximize the overall profits of processed jobs while respecting machine constraints. A first-in- first-out heuristic is applied to find an initial solution, and then a large neighborhood search procedure is employed to relax and re- optimize cumbersome solutions. A machine learning mechanism is also introduced to converge on the most efficient neighborhoods for the problem. Extensive computational results are presented based on data from an application involving the daily observation scheduling of a fleet of earth observing satellites. The method rapidly solves most problem instances to optimal or near optimal and shows a robust performance in sensitive analysis.

Identical Machine Scheduling Problem with Sequence-Dependent Setup Times: MILP Formulations Computational Study

This work aims to give a systematic construction of the two families of mixed-integer-linear-programming (MILP) formulations, which are graph- based and sequence-based, of the well-known scheduling problem. Two upper bounds of job completion times are introduced. A numerical test result analysis is conducted with a two-fold objective 1) testing the performance of each solving methods, and 2) identifying and analyzing the tractability of an instance according to the instance structure in terms of the number of machines, of the jobs setup time lengths and of the jobs release date distribution over the scheduling horizon.

Generalized multiple time windows model based parallel machine scheduling for TDRSS

The scheduling efficiency of the tracking and data relay satellite system（TDRSS）is strictly limited by the scheduling degrees of freedom（DoF）,including time DoF defined by jobs＇ flexible time windows and spatial DoF brought by multiple servable tracking and data relay satellites（TDRSs）.In this paper,ageneralized multiple time windows（GMTW）model is proposed to fully exploit the time and spatial DoF.Then,the improvements of service capability and job-completion probability based on the GMTW are theoretically proved.Further,an asymmetric path-relinking（APR）based heuristic job scheduling framework is presented to maximize the usage of DoF provided by the GMTW.Simulation results show that by using our proposal 11%improvement of average jobcompletion probability can be obtained.Meanwhile,the computing time of the time-to-target can be shorten to 1/9 of the GRASP.

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （PART I：EQUAL TIMES AND COSTS）

Abstract Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by reallocating resources. In this paper, authors consider a machine scheduling problem with controllable processing times. In the first part of this paper, a special case where the processing times and compression costs are uniform among jobs is discussed. Theoretical results are derived that aid in developing an O(n 2) algorithm to slove the problem optimally. In the second part of this paper, authors generalize the discussion to general case. An effective heuristic to the general problem will be presented.

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS ： PROOF OF THEOREMS

Abstract This report is virtually the appendix part of the author's previous paper which includes the proofs for the theorems and lemmas.

MODIFIED BOTTLENECK-BASED PROCEDURE FOR LARGE-SCALE FLOW-SHOP SCHEDULING PROBLEMS WITH BOTTLENECK

A new bottleneck-based heuristic for large-scale flow-shop scheduling problems with a bottleneck is proposed, which is simpler but more tailored than the shifting bottleneck （SB） procedure. In this algorithm, a schedule for the bottleneck machine is first constructed optimally and then the non-bottleneck machines are scheduled around the bottleneck schedule by some effective dispatching rules. Computational results show that the modified bottleneck-based procedure can achieve a tradeoff between solution quality and computational time comparing with SB procedure for medium-size problems. Furthermore it can obtain a good solution in quite short time for large-scale scheduling problems.

Adaptive subsequence adjustment with evolutionary asymmetric path-relinking for TDRSS scheduling

Due to the limited transmission resources for data relay in the tracking and data relay satellite system （TDRSS）, there are many job requirements in busy days which will be discarded in the conventional job scheduling model. Therefore, the improvement of scheduling efficiency in the TDRSS can not only help to increase the resource utilities, but also to reduce the scheduling failure ratio. A model of nonhomogeneous parallel machines scheduling problems with time window （NPM-TW） is firstly built up for the TDRSS, considering the distinct features of the variable preparation time and the nonhomogeneous transmission rates for different types of antennas on each tracking and data relay satellite （TDRS）. Then, an adaptive subsequence adjustment （ASA） framework with evolutionary asymmetric path-relinking （EvAPR） is proposed to solve this problem, in which an asymmetric progressive crossover operation is involved to overcome the local optima by the conventional job inserting methods. The numerical results show that, compared with the classical greedy randomized adaptive search procedure （GRASP） algorithm, the scheduling failure ratio of jobs can be reduced over 11% on average by the proposed ASA with EvAPR.

Hybrid Genetic Algorithms with Fuzzy Logic Controller

In this paper, a new implementation of genetic algorithms (GAs) is developed for the machine scheduling problem, which is abundant among the modern manufacturing systems. The performance measure of early and tardy completion of jobs is very natural as one's aim, which is usually to minimize simultaneously both earliness and tardiness of all jobs. As the problem is NP-hard and no effective algorithms exist, we propose a hybrid genetic algorithms approach to deal with it. We adjust the crossover and mutation probabilities by fuzzy logic controller whereas the hybrid genetic algorithm does not require preliminary experiments to determine probabilities for genetic operators. The experimental results show the effectiveness of the GAs method proposed in the paper.