A robust approach for the single machine scheduling problem

This paper describes a robust approach for the single machine scheduling problem 1|r _i |L _max. The method is said to be robust since it characterizes a large set of optimal solutions allowing to switch from one solution to another, without any performance loss, in order to face potential disruptions which occur during the schedule execution. It is based on a dominance theorem that characterizes a set of dominant sequences, using the interval structure defined by the relative order of the release and the due dates of jobs. The performance of a set of dominant sequences can be determined in polynomial time by computing the most favorable and the most unfavorable sequences associated with each job, with regard to the lateness criterion. A branch and bound procedure is proposed which modifies the interval structure of the problem in order to tighten the dominant set of sequences so that only the optimal sequences are conserved.     

Multi-product valid inequalities for the discrete lot-sizing and scheduling problem

We consider a problem arising in the context of industrial production planning, namely the multi-product discrete lot-sizing and scheduling problem with sequence-dependent changeover costs. We aim at developing an exact solution approach based on a Cut & Branch procedure for this combinatorial optimization problem. To achieve this, we propose a new family of multi-product valid inequalities which corresponds to taking into account the conflicts between different products simultaneously requiring production on the resource. We then present both an exact and a heuristic separation algorithm which form the basis of a cutting-plane generation algorithm. We finally discuss computational results which confirm the practical usefulness of the proposed inequalities at strengthening the MILP formulation and at reducing the overall computation time.     

A simulated annealing algorithm for single machine scheduling problems with family setups

Motivated by the real-life scheduling problem in a steel-wire factory in China, this paper studies the problem of minimizing the maximum lateness on a single machine with family setups. In view of the NP-hard nature of the problem, neighborhood properties of the problem are investigated. It is found that the traditional move-based neighborhood is inefficient to search. Then a new neighborhood, which is based on batch destruction and construction, is developed. A simulated annealing algorithm with the new neighborhood is proposed. Experiments are carried out on the randomly generated problems and the real-life instances from a factory in China. Computational results show that the proposed algorithm can obtain better near optimal solutions than the existing algorithm.     

Knowledge-based single machine scheduling

Production scheduling remains as one of the most important functions in manufacturing systems. Knowledge-based systems provide new insight to production scheduling. The increasing complexity of selecting the right procedure, understanding the procedure and solving an instant can be simplified with the help of knoweldge-based expert systems. This paper explains a prototype system developed using a rule-based expert system shell, M.1, for an application limited to single machine scheduling only.     

Two branch-and-bound algorithms for the robust parallel machine scheduling problem

Uncertainty is an inevitable element in many practical production planning and scheduling environments. When a due date is predetermined for performing a set of jobs for a customer, production managers are often concerned with establishing a schedule with the highest possible confidence of meeting the due date. In this paper, we study the problem of scheduling a given number of jobs on a specified number of identical parallel machines when the processing time of each job is stochastic. Our goal is to find a robust schedule that maximizes the customer service level, which is the probability of the makespan not exceeding the due date. We develop two branch-and-bound algorithms for finding an optimal solution; the two algorithms differ mainly in their branching scheme. We generate a set of benchmark instances and compare the performance of the algorithms based on this dataset.     

单机调度问题对偶集结迭代算法

具有到达时间约束、目标为最小化加权完工时间之和的单机调度问题是一个典型的NP-hard问题,采用时间下标建模的线性规划松弛方法可提供一个很强的下界,但优化求解存在维数困难.为此,本文提出了一种对偶集结优化策略,通过选择一个衰减集结矩阵集结对偶乘子变量,利用对偶理论获得模型的约束集结,从而降低计算复杂度.同时分析了集结模型的结构特性,并提出一种迭代算法来改善下界.仿真结果表明对偶集结迭代算法能够减少计算时间,同时改善下界性能,适用于大规模调度问题.     

Dynamic non-preemptive single machine scheduling

Considering a dynamic single machine problem in which operations cannot be split, we first develop a decision theory based heuristic called DT-TD (Decision Theory-Tactically Delayed) of computational complexity O(n²). Using a simple look-ahead procedure, it produces, actically delayed (TD) schedules. We then develop a branch-and-bound (BB) algorithm (which uses DT-TD to obtain the initial upper bound) to obtain the optimum schedule. The optimum schedules are examined to identify conditions where TD schedules are necessary. Results based on 540 test problems suggest that TD schedules are important, for job shop scheduling under the range of conditions examined, when due dates are arbitrary and utilization is low. Additional test results indicate that the difference between the optimum schedule and the optimum non-delay schedule could be substantial. Finally, the performance of the DT-TD heuristic is analyzed by comparing its solution to the optimum solution obtained using the BB algorithm. The results indicate that the DT-TD heuristic is effective.     

A genetic algorithm for JIT single machine scheduling with preemption and machine idle time

This paper concerns with the concept of preemption in just-in-time single machine scheduling problem, with allowable machine idle time. We proposed a new model, with non-linear terms and integer variables which cannot be solved efficiently for large size problems due to its NP-hardness. To solve the model for real size applications, genetic algorithm is applied. These genetic procedures are also quite close to the optimum and provided an optimal solution for most of the test problems. Numerical examples show that the proposed algorithm is efficient and effective.     

A hybrid heuristic approach for single machine scheduling with release times

In this work we consider the well-known one-machine total completion time sequencing problem subject to release times. We present a very large scale neighborhood search heuristic based on mathematical programming. This heuristic makes use of the positional completion time formulation of the problem in which valid inequalities are added. The proposed procedure compares favorably with the state of the art heuristics.     

Meta-heuristics for stable scheduling on a single machine

This paper presents a model for single-machine scheduling with stability objective and a common deadline. Job durations are uncertain, and our goal is to ensure that there is little deviation between planned and actual job starting times. We propose two meta-heuristics for solving an approximate formulation of the model that assumes that exactly one job is disrupted during schedule execution, and we also present a meta-heuristic for the global problem with independent job durations.     

Lot scheduling on a single machine

In a practical situation, a manufacturer receives different orders from its customers. Different orders may contain different quantities of the product. Therefore, the manufacturer has to decide how to group these orders into different lots based on the capacity of the lot processing machine (such as integrated circuit tester, heated container, etc.) and then decides the sequence of these lots. In this paper, we study a lot scheduling problem with orders which can be split. The objective is to minimize the total completion time of all orders. We show that this problem can be solved in polynomial time.     

Metaheuristics for the single machine weighted quadratic tardiness scheduling problem

This paper considers the single machine scheduling problem with weighted quadratic tardiness costs. Three metaheuristics are presented, namely iterated local search, variable greedy and steady-state genetic algorithm procedures. These address a gap in the existing literature, which includes branch-and-bound algorithms (which can provide optimal solutions for small problems only) and dispatching rules (which are efficient and capable of providing adequate solutions for even quite large instances). A simple local search procedure which incorporates problem specific information is also proposed.The computational results show that the proposed metaheuristics clearly outperform the best of the existing procedures. Also, they provide an optimal solution for all (or nearly all, in the case of the variable greedy heuristic) the smaller size problems. The metaheuristics are quite close in what regards solution quality. Nevertheless, the iterated local search method provides the best solution, though at the expense of additional computational time. The exact opposite is true for the variable greedy procedure, while the genetic algorithm is a good all-around performer.     

Tabu search methods for a single machine scheduling problem

In this paper we discuss the use of three local search strategies within a tabu search (TS) method for the approximate solution of a single machine scheduling problem. The problem consists of minimizing the sum of the set-up costs and linear delay penalties whenN jobs, arriving at time zero, are to be scheduled for sequential processing on a continuously available machine. Following a review of a previous study of this problem, we first consider a TS method that uses the common approach of making a succession of pairwise job exchanges, or swaps, to move from one trial solution to another. Next, we consider the use of insert moves to define the local neighborhood of each trial solution. These moves consist of transferring a single job from one position to another in the schedule. Finally, we construct a TS method (TS-hybrid) that employs both swap and insert moves. Experiments with benchmark problems of up to 60 jobs illustrate that there is an advantage in using more than one strategy to move from one trial solution to another within a TS method.This work was begun during the author's summer internship at the Advanced Knowledge Systems Group of US West Advanced Technologies.     

Mixed integer programming formulations for single machine scheduling problems

In this paper, the computational performance of four different mixed integer programming (MIP) formulations for various single machine scheduling problems is studied. Based on the computational results, we discuss which MIP formulation might work best for these problems. The results also reveal that for certain problems a less frequently used MIP formulation is computationally more efficient in practice than commonly used MIP formulations. We further present two sets of inequalities that can be used to improve the formulation with assignment and positional date variables.     

Pseudopolynomial algorithms for CTV minimization in single machine scheduling

The problem of scheduling jobs on a single machine so as to minimize completion time variance (CTV) is considered. In this article, we have derived two dominance criteria and used them in the development of a new pseudopolynomial algorithm. This algorithm is an implicit enumeration scheme based on a binary branching strategy, with larger jobs fixed at early stages, and is superior to those of De, Ghosh and Wells [1] and Kubiak [2] in terms of computational complexity. It is observed that this algorithm is very good when the job processing times are quite heterogeneous, while the algorithm of De, Ghosh and Wells [1] is excellent for homogeneous processing times. By making use of these contrasting merits, another pseudopolynomial algorithm is then proposed. Results of extensive numerical investigation on the performances of the algorithms are also reported.     

A single machine carryover sequence-dependent group scheduling in PCB manufacturing

This paper considers the problem of minimizing the makespan on a single machine with carryover sequence-dependent setup times. A similar problem with multi-machine flow shop usually arises in the assembly of printed circuit boards (PCBs). This research investigates the possibility of processing all components of PCBs using just one machine. By doing so the operational costs of having multi-machines can be reduced, and as a result, finding an optimal solution might be more plausible. The objective is to minimize the maximum completion time of all board groups, commonly known as makespan. The operational constraints are such that all board types within a board group must be completely kitted, as it is traditionally performed by kitting staff, before that board group begins its assembly operation. We introduce the external setup (kitting) time and require that it be performed solely by the machine operator during the run time of the current board group, and thereby completely eliminating the need for kitting staff. The carryover sequence-dependent setup time, namely the internal (machine) setup time, is realized when a new board group is ready for assembly operation and is dependent on all of the previously scheduled board groups and their sequences. To the best of our knowledge, this is the first time the external and internal setup times are integrated in PCB group scheduling research. We develop a branch-and-bound algorithm and a lower-bounding structure. The lower bound consists of two approaches, which enable the algorithm to simultaneously reduce performing unnecessary exploration. In order to test the efficiency of the algorithm, several problem instances with different board groups have been used. The algorithm developed requires a significantly large computation time to optimally solve very large problems. Thus to speak for the efficiency in terms of solving comparable large industry-size problems, we evaluate the deviation of the algorithm from the lower bound which turns out to be very small, with an average of only 6%, in all of the problem instances considered.     

A hybrid metaheuristic for the prize-collecting single machine scheduling problem with sequence-dependent setup times

This paper investigates a single machine scheduling problem with strong industrial background, named the prize-collecting single machine scheduling problem with sequence-dependent setup times. In this problem, there are n candidate jobs for processing in a single machine, each job has a weight (or profit) and a processing time, and during processing a symmetric sequence-dependent setup time exists between two consecutive jobs. Since there is a maximum available time limitation of the machine, it is generally impossible to complete the processing of all the candidate jobs within this time limitation. The objective is to find a job processing sequence of maximal job weights (or profits) over a subset of all candidate jobs whose makespan does not exceed the given time limitation. This problem can be considered as an application of the orienteering problem (OP) in the field of discrete manufacturing. We formulate this problem as a mixed integer linear programming (MILP) model and propose a hybrid metaheuristic combining the structures of scatter search and variable neighborhood search. Computational results on a large number of randomly generated instances with different structures show that the proposed hybrid metaheuristic outperforms CPLEX and two metaheuristics proposed for the OP.     

A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times

This paper presents a hybrid approach based on the integration between a genetic algorithm (GA) and concepts from constraint programming, multi-objective evolutionary algorithms and ant colony optimization for solving a scheduling problem. The main contributions are the integration of these concepts in a GA crossover operator. The proposed methodology is applied to a single machine scheduling problem with sequence-dependent setup times for the objective of minimizing the total tardiness. A sensitivity analysis of the hybrid approach is carried out to compare the performance of the GA and the hybrid genetic algorithm (HGA) approaches on different benchmarks from the literature. The numerical experiments demonstrate the HGA efficiency and effectiveness which generates solutions that approach those of the known reference sets and improves several lower bounds.     

Jackson's semi-preemptive scheduling on a single machine

We propose an effective improvement of the well-known Jackson's preemptive schedule lower bound for the single machine scheduling problem with heads and tails. The semi-preemptive scheduling concept roughly consists in reducing the preemption impact by constraining some particular job parts to be processed in reduced time intervals. The impact of semi-preemptive scheduling is twofold: it yields a lower bound which dominates the preemptive one, and enables more effective adjustments of the heads and tails. Our experimental study revealed that suitably embedding our procedure within Carlier's algorithm makes feasible to solve all of the hard instances which could not be solved by its original variant.