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.

A hybrid two-stage fexible flowshop scheduling problem with m identical parallel machines and a burn-in processor separately

A hybrid two-stage flowshop scheduling problem was considered which involves m identical parallel machines at Stage 1 and a burn-in processor M at Stage 2, and the makespan was taken as the minimization objective. This scheduling problem is NP-hard in general. We divide it into eight subcases. Except for the following two subcases： （1） b≥ an, max{m, B} 〈 n; （2） a1 ≤ b ≤ an, m ≤ B 〈 n, for all other subcases, their NP-hardness was proved or pointed out, corresponding approximation algorithms were conducted and their worst-case performances were estimated. In all these approximation algorithms, the Multifit and PTAS algorithms were respectively used, as the jobs were scheduled in m identical parallel machines.

Performance analysis of active schedules in identical parallel machine

Active schedule is one of the most basic and popular concepts in production scheduling research. For identical parallel machine scheduling with jobs＇ dynamic arrivals, the tight performance bounds of active schedules under the measurement of four popular objectives are respectively given in this paper. Similar analysis method and conclusions can be generalized to static identical parallel machine and single machine scheduling problem.

Scheduling Multiple Orders per Job with Multiple Constraints on Identical Parallel Machines

With a comprehensive consideration of multiple product types, past-sequence-dependent （ p-s-d ） setup times, and deterioration effects constraints in processes of wafer fabrication systems, a novel scheduling model of multiple orders per job（MOJ） on identical parallel machines was developed and an immune genetic algorithm（IGA） was applied to solving the scheduling problem. A scheduling problem domain was described. A non-linear mathematical programming model was also set up with an objective function of minimizing total weighted earliness-tardlness penalties of the system. On the basis of the mathematical model, IGA was put forward. Based on the genetic algorithm （GA）, the proposed algorithm （IGA） can generate feasible solutions and ensure the diversity of antibodies. In the process of immunization programming, to guarantee the algorithm＇s convergence performance, the modified rule of apparent tardiness cost with setups （ATCS） was presented. Finally, simulation experiments were designed, and the results indicated that the algorithm had good adaptability when the values of the constraints＇ characteristic parameters were changed and it verified the validity of the algorithm.

ON-LINE SCHEDULING WITH REJECTION ON IDENTICAL PARALLEL MACHINES

In this paper, we consider the on-line scheduling of unit time jobs with rejection on rn identical parallel machines. The objective is to minimize the total completion time of the accepted jobs plus the total penalty of the rejected jobs. We give an on-line algorithm for the problem with competitive ratio 1/2 （2 ＋√3） ≈ 1.86602.

AN IMPROVED BRANCH-AND-BOUND ALGORITHM TO MINIMIZE THE WEIGHTED FLOWTIME ON IDENTICAL PARALLEL MACHINES WITH FAMILY SETUP TIMES

This article investigates identical parallel machines scheduling with family setup times. The objective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a constructive heuristic algorithm and three complementary lower bounds. Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family, while the third one is based on a lagrangian relaxation. The bounds and the heuristic are incorporated into a branch-and-bound algorithm. Experimental results obtained outperform those of the methods presented in previous works, in term of size of solved problems.