Scheduling open shops with parallel machines to minimize total completion time

This paper explores scheduling a realistic variant of open shops with parallel machines per working stage. Since real production floors seldom employ a single machine for each operation, the regular open shop problem is very often in practice extended with a set of parallel machines at each stage. The purpose of duplicating machines in parallel is to either eliminate or to reduce the impact of bottleneck stages on the overall shop efficiency. The objective is to find the sequence which minimizes total completion times of jobs. We first formulate the problem as an effective mixed integer linear programming model, and then we employ memetic algorithms to solve the problem. We employ Taguchi method to evaluate the effects of different operators and parameters on the performance of memetic algorithm. To further enhance the memetic algorithm, we hybridize it with a simple form of simulated annealing as its local search engine. To assess the performance of the model and algorithms, we establish two computational experiments. The first one is small-sized instances by which the model and general performance of the algorithms are evaluated. The second one consists of large-sized instances by which we further evaluate the algorithms.     

Scheduling on parallel identical machines to minimize total tardiness

This paper focuses on the problem of scheduling n independent jobs on m identical parallel machines for the objective of minimizing total tardiness of the jobs. We develop dominance properties and lower bounds, and develop a branch and bound algorithm using these properties and lower bounds as well as upper bounds obtained from a heuristic algorithm. Computational experiments are performed on randomly generated test problems and results show that the algorithm solves problems with moderate sizes in a reasonable amount of computation time.     

Scheduling open shops with parallel machines

The parallel shop and the open shop are two machine environments that have received much attention in the literature of scheduling theory. A common generalization—the open shop with parallel machines—is considered in this paper. Polynomial-time algorithms are presented for obtaining minimum-length preemptive schedules for three cases. Open shops with single-operation machines of equal speed are scheduled with essentially no more difficulty than an ordinary open shop. Open shops with multiple-operation machines of equal speed are scheduled with the aid of a sequence of network flow computations. The general open shop problem with parallel machines of arbitrary speeds can be solved by linear programming, in much the same way as an optimal preemptive schedule can be found for unrelated parallel machines.     

Preemptive scheduling of two uniform parallel machines to minimize total tardiness

We consider the problem of preemptive scheduling n jobs on two uniform parallel machines. All jobs have equal processing requirements. For each job we are given its due date. The objective is to find a schedule minimizing total tardiness ∑T_i. We suggest an O(n log n) algorithm to solve this problem.     

Single machine scheduling with family setups to minimize total earliness and tardiness

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize total earliness and tardiness when family setup times exist. The paper proposes optimal branch-and-bound algorithms for both the group technology assumption and if the group technology assumption is removed. A heuristic algorithm is proposed to solve larger problems with the group technology assumption removed. The proposed algorithms were empirically evaluated on problems of various sizes and parameters. The paper also explores how the choice of procedure affects total earliness and tardiness if an implementation of lean production methods has resulted in a reduction in setup times. An important finding of these empirical investigations is that scheduling jobs by removing the group technology assumption can significantly reduce total earliness and tardiness.     

A note on the equivalence of two heuristics to minimize total tardiness

Over the last thirty years, many researchers have studied single machine static and deterministic scheduling with the objective of minimizing total tardiness. It has been established that the tardiness problem is NP-hard. So it is unlikely that a polynomial time algorithm can be found for developing optimal solutions to this problem. The Modified Due Date rule (MDD) is generally considered to be an efficient heuristic that deals with the tardiness problem. Recently, Panwalkar et al. have proposed the PSK rule as effective in dealing with tardiness. The purpose of this paper is to show that the PSK rule is an implementation of the MDD rule. Furthermore, the relationship between the MDD rule and the WI (Wilkeson and Irwin) rule is clarified.     

A penalty-shift-insertion-based algorithm to minimize total flow time in no-wait flow shops

This paper proposes a penalty-shift-insertion (PSI)-based algorithm for the no-wait flow shop scheduling problem to minimize total flow time. In the first phase, a penalty-based heuristic, derived from Vogel’s approximation method used for the classic transportation problem is used to generate an initial schedule. In the second phase, a known solution is improved using a forward shift heuristic. Then the third phase improves this solution using a job-pair and a single-job insertion heuristic. Results of the computational experiments with a large number of randomly generated problem instances show that the proposed PSI algorithm is relatively more effective and efficient in minimizing total flow time in a no-wait flow shop than the state-of-the-art procedures. Statistical significance of better results obtained by the proposed algorithm is also reported.     

Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness

Parallel machine scheduling is a popular research area due to its wide range of potential application areas. This paper focuses on the problem of scheduling n independent jobs to be processed on m identical parallel machines with the aim of minimizing the total tardiness of the jobs considering a job splitting property. It is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. We present a mathematical model for this problem. The problem of total tardiness on identical parallel machines is NP-hard. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using an optimization solver is extremely difficult. We propose two meta-heuristics: Tabu search and simulated annealing. Computational results are compared on random generated problems with different sizes.     

A new dominance rule to minimize total weighted tardiness with unequal release dates

We present a new dominance rule by considering the time-dependent orderings between each pair of jobs for the single machine total weighted tardiness problem with release dates. The proposed dominance rule provides a sufficient condition for local optimality. Therefore, if any sequence violates the dominance rule then switching the violating jobs either lowers the total weighted tardiness or leaves it unchanged. We introduce an algorithm based on the dominance rule, which is compared to a number of competing heuristics for a set of randomly generated problems. Our computational results indicate that the proposed algorithm dominates the competing algorithms in all runs, therefore it can improve the upper bounding scheme in any enumerative algorithm. The proposed time-dependent local dominance rule is also implemented in two local search algorithms to guide these algorithms to the areas that will most likely contain the good solutions.     

Scheduling a hybrid assembly-differentiation flowshop to minimize total flow time

This study considers a hybrid assembly-differentiation flowshop scheduling problem (HADFSP), in which there are three production stages, including components manufacturing, assembly, and differentiation. All the components of a job are processed on different machines at the first stage. Subsequently, they are assembled together on a common single machine at the second stage. At the third stage, each job of a particular type is processed on a dedicated machine. The objective is to find a job schedule to minimize total flow time (TFT). At first, a mixed integer programming (MIP) model is formulated and then some properties of the optimal solution are presented. Since the NP-hardness of the problem, two fast heuristics (SPT-based heuristic and NEH-based heuristic) and three hybrid meta-heuristics (HGA-VNS, HDDE-VNS and HEDA-VNS) are developed for solving medium- and large-size problems. In order to evaluate the performances of the proposed algorithms, a lower bound for the HADFSP with TFT criteria (HADFSP-TFT) is established. The MIP model and the proposed algorithms are compared on randomly generated problems. Computational results show the effectiveness of the MIP model and the proposed algorithms. The computational analysis indicates that, in average, the HDDE-VNS performs better and more robustly than the other two meta-heuristics, whereas the NEH heuristic consume little time and could reach reasonable solutions.     

A Branch-and-Bound procedure to minimize total tardiness on one machine with arbitrary release dates

In this paper, we present a Branch-and-Bound procedure to minimize total tardiness on one machine with arbitrary release dates. We introduce new lower bounds and we generalize some well-known dominance properties. Our procedure handles instances as large as 500 jobs although some 60 jobs instances remain open. Computational results show that the proposed approach outperforms the best known procedures.     

Scheduling start time dependent jobs to minimize the total weighted completion time

This paper deals with a single machine scheduling problem with start time dependent job processing times. The job processing times are characterized by decreasing linear functions dependent on their start times. The problem is to find a schedule for which the total weighted completion time is minimized. It is proved that the problem is NP-hard. Some properties of special cases of the general problem are also given. Based on these results, two heuristic algorithms are constructed and their performance is compared.     

Scheduling orders for multiple product types to minimize total weighted completion time

We consider the problem of scheduling orders for multiple different product types in an environment with m dedicated machines in parallel. The objective is to minimize the total weighted completion time. Each product type is produced by one and only one of the m dedicated machines; that is, each machine is dedicated to a specific product type. Each order has a weight and may also have a release date. Each order asks for certain amounts of various different product types. The different products for an order can be produced concurrently. Preemptions are not allowed. Even when all orders are available at time 0, the problem has been shown to be strongly NP-hard for any fixed number (?2) of machines. This paper focuses on the design and analysis of efficient heuristics for the case without release dates. Occasionally, however, we extend our results to the case with release dates. The heuristics considered include some that have already been proposed in the literature as well as several new ones. They include various static and dynamic priority rules as well as two more sophisticated LP-based algorithms. We analyze the performance bounds of the priority rules and of the algorithms and present also an in-depth comparative analysis of the various rules and algorithms. The conclusions from this empirical analysis provide insights into the trade-offs with regard to solution quality, speed, and memory space.     

Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness

We consider the problem of scheduling n preemptive jobs on a single machine to minimize total tardiness, subject to agreeable due dates, i.e., a later release date corresponds to a later due date. We prove that the problem is -hard in the ordinary sense by showing that it is -hard, and deriving a pseudo-polynomial algorithm for it.     

Scheduling multiple orders per job in a single machine to minimize total completion time

This paper deals with a single-machine scheduling problem with multiple orders per job (MOJ) considerations. Both lot processing machines and item processing machines are also examined. There are two primary decisions that must be made in the proposed problem: (1) how to group the orders together, and (2) how to schedule the jobs once they are formed. In order to obtain the optimal solution to a scheduling problem, these two decisions should be made simultaneously. The performance measure is the total completion time of all orders. Two mixed binary integer programming models are developed to optimally solve this problem. Also, two efficient heuristics are proposed for solving large-sized problems. Computational results are provided to demonstrate the efficiency of the models and the effectiveness of the heuristics.     

Note on Shim and Kim’s lower bounds for scheduling on identical parallel machines to minimize total tardiness

This note introduces a new lower bound for the problem of scheduling on parallel identical machines to minimize total tardiness that is based on the concepts used in the two lower bounds developed by Shim and Kim [Shim, S.O., Kim, Y.D., 2007. Scheduling on parallel identical machines to minimize total tardiness. European Journal of Operational Research 177, 135–146]. The note shows that the new lower bound dominates the three lower bounds used in Shim and Kim’s branch-and-bound algorithm and can be used in place of these lower bounds to lower the enumeration required.     

Scheduling in network flow shops

We consider the general problem of static scheduling of a set of jobs in a network flow shop. In network flow shops, the scheduler not only has to sequence and schedule but also must concurrently determine the process routing of the jobs through the shop. In this paper, we establish the computational complexity of this new class of scheduling problem and propose a general purpose heuristic procedure. The performance of the heuristic is analyzed when makespan, cycle time and average flow time are the desired objectives.This research has been supported by the UCLA Academic Senate Grant #95.     

带有固定区间的单机双代理可中断总误工问题

研究带有固定区间的两个代理单机排序问题.第一个代理工件可中断,且工件到达时间与工期满足一致关系,目标函数为最小化总误工.第二个代理工件被安排在固定时间窗口.目标是寻找一个排序,使得满足第二个代理目标可行情况下,第一个代理目标函数值最小.在固定区间等于加工时间的情况下,利用分块原则,提出了一个伪多项式时间动态规划算法,并给出了固定区间大于加工时间情况下的时间复杂度分析.     

A heuristic for scheduling general job shops to minimize maximum lateness

Based on the various priority dispatching rules, three dominant rules were formulated. Heuristic approaches were developed based on these dominant rules and dominant matrix. These heuristics can solve problems where a job may need to be processed by the same machine more than once in its operation sequence and different release times are allowed for different machines. The proposed heuristics appear to be fairly effective procedures, and various numerical results are obtained and compared with the various dispatching rules and with a branch and bound approach.