Using two-machine flowshop with maximum lateness objective to model multimedia data objects scheduling problem for WWW applications

The multimedia data objects scheduling problem for WWW applications is modeled using the two-machine flowshop problem of minimizing maximum lateness with separate setup times. We establish three dominance relations, and propose four heuristics. Also, we conduct computational experiments to compare the performance of the proposed heuristics and that of existing ones in the literature. The results of the computational experiments show that the proposed heuristics are quite efficient.Scope and purposeA two-machine flowshop scheduling problem involves scheduling a number of jobs on the machines in order to optimize a given criterion. The majority of research assumes that setup times are negligible or can be combined with the processing times. However, the latter assumption is invalid since it may lead to more idle time on the second machine. In the literature, the separate setup times problem has been mainly addressed with the completion-time-related objective functions such as makespan. However, there are many real-life situations in which a due-date-related objective function such as maximum lateness is more appropriate. The problem with maximum lateness objective has received limited attention from researchers as indicated by a recent survey paper. In this paper, we show a real-life situation in the Internet where the two-machine flowshop problem of minimizing maximum lateness with separate setup times can be used to model the multimedia object scheduling problem. We propose new improved heuristics for this problem and compare with existing ones in the literature.     

A new heuristic and dominance relations for no-wait flowshops with setups

The two-machine no-wait flowshop problem, where setup times are considered separate from processing times and sequence independent, is addressed with respect to minimizing total flowtime. A local and a global dominance relation are developed and a new heuristic is provided. Furthermore, a lower bound is obtained and used along with the dominance relations in a branch-and-bound algorithm in order to evaluate the efficiency of the heuristic. Computational experience demonstrates the superiority of the local dominance relation and the new heuristic.Scope and purposeNo-wait flowshop problems, where jobs have to be processed without interruption between consecutive machines, represent an important area in scheduling. There are several industries where the no-wait flowshop problem applies including the metal, plastic, and chemical industries. For instance, in the case of steel production, the heated metal must continuously go through a sequence of operations before it is cooled in order to prevent defects in the composition of the material. Another important area arises when setup time is considered separate from processing time. Such a consideration is particularly justified when the ratio of setup to processing time is non-negligible. Many applications warrant separate consideration of setup; examples include the re-tooling of multi-tool equipment. Other applications can be found in textile, plastic, chemical, and semi-conductor industries. This paper develops a new heuristic and dominance relations for the two-machine no-wait separate setup flowshop problem, where the performance criterion is total flowtime.     

The Tricriteria Two-Machine Flowshop Scheduling Problem

The literature on the two-machine flowshop scheduling problem reveals that the problem has been addressed with bicriteria of either makespan and mean flowtime or makespan and maximum tardiness (lateness). This paper extends the problem to all the three criteria (tricriteria) where the objective is to minimize a weighted sum of makespan, mean flowtime, and maximum lateness. A dominance relation and a lower bound are established. The dominance relation and the lower bound are used to develop a branch-and-bound algorithm. The dominance relation is also used to develop several heuristics. An extensive computational analysis is conducted to evaluate the performance of the dominance relation and the heuristics. The analysis shows that the dominance relation is effective. The analysis also shows that the heuristics are quite efficient, and some heuristics have an error of less than 1%. Moreover, these heuristics have the desirable property that the error does not increase by the number of jobs.     

Two-machine flowshop scheduling with job class setups to minimize total flowtime

This paper studies the two-machine flowshop scheduling problem with job class setups to minimize the total flowtime. The jobs are classified into classes, and a setup is required on a machine if it switches processing of jobs from one class to another class, but no setup is required if the jobs are from the same class. For some special cases, we derive a number of properties of the optimal solution, based on which we design heuristics and branch-and-bound algorithms to solve these problems. Computational results show that these algorithms are effective in yielding near-optimal or optimal solutions to the tested problems.     

A memetic algorithm for the re-entrant permutation flowshop scheduling problem to minimize the makespan

A common assumption in the classical permutation flowshop scheduling model is that each job is processed on each machine at most once. However, this assumption does not hold for a re-entrant flowshop in which a job may be operated by one or more machines many times. Given that the re-entrant permutation flowshop scheduling problem to minimize the makespan is very complex, we adopt the CPLEX solver and develop a memetic algorithm (MA) to tackle the problem. We conduct computational experiments to test the effectiveness of the proposed algorithm and compare it with two existing heuristics. The results show that CPLEX can solve mid-size problem instances in a reasonable computing time, and the proposed MA is effective in treating the problem and outperforms the two existing heuristics.     

A branch-and-bound algorithm for the three-machine flowshop scheduling problem with bicriteria of makespan andtotal flowtime

This paper addresses the three‐machine flowshop scheduling problem with a bicriteria of minimizing a weighted sum of makespan and total flowtime. Three lower bounds, an upper bound, and several dominance relations are developed. The upper bound is developed using a two‐phase hybrid heuristic method. A branch‐and‐bound algorithm, incorporating the developed bounds and dominance relations, is presented. An extensive computational analysis on randomly generated problems is conducted. The analysis indicates that the proposed bounds, dominance relations, and branch‐and‐bound algorithm are efficient.     

两机无等待流水车间调度问题的性质

针对两机无等待流水车间调度问题,提出目标函数最大完工时间最小化的快速算法,并给出算法的复杂度。分析两机无等待流水车间调度问题的排列排序性质,证明了两机无等待流水车间调度问题的可行解只存在于排列排序中,排列排序的最优解一定是两机无等待流水车间调度问题的最优解。最后研究了同时包含普通工件和无等待工件的两机流水车间调度问题的复杂性,为进一步研究两机无等待流水车间调度问题提供了理论依据。     

Permutation flowshop scheduling problems with maximal and minimal time lags

In this paper, we study permutation flowshop problems with minimal and/or maximal time lags, where the time lags are defined between couples of successive operations of jobs. Such constraints may be used to model various industrial situations, for instance the production of perishable products. We present theoretical results concerning two-machine cases, we prove that the two-machine permutation flowshop with constant maximal time lags is strongly NP-hard. We develop an optimal branch and bound procedure to solve the m$m$-machine permutation flowshop problem with minimal and maximal time lags. We test several lower bounds and heuristics providing upper bounds on different classes of benchmarks, and we carry out a performance analysis.     

Note on minimizing total tardiness in a two-machine flowshop

This note considers the problem of sequencing jobs to minimize total tardiness in a two-machine flowshop. The note shows how three dominance conditions and a lower bound previously developed for this problem can be improved. The note also proposes a new dominance condition. A branch-and-bound algorithm is developed that uses the improvements and new dominance condition. The algorithm is tested on randomly generated problems and the results of the test show that the improvements and new dominance condition improves the branch-and-bound algorithm's efficiency.     

Two-machine robotic cell scheduling problem with sequence-dependent setup times

In this paper, we introduce a new and practical two-machine robotic cell scheduling problem with sequence-dependent setup times (2RCSDST) along with different loading/unloading times for each part. Our objective is to simultaneously determine the sequence of robot moves and the sequence of parts that minimize the total cycle time. The proposed problem is proven to be strongly NP-hard. Using the Gilmore and Gomory (GnG) algorithm, a polynomial-time computable lower bound is provided.     

Non-permutation flowshop scheduling with dual resources

Typically, in order to process jobs in a flowshop both machines and labor are required. However, in traditional scheduling problems, labor is assumed to be plentiful and only machine is considered to be a constraint. This assumption could be due to the lower cost of labor compared to machines or the complexity of dual-resource constrained problems. In this paper a mathematical model is developed to minimize the work-in-process inventory while maximizing the service level in a flowshop with dual resources. The model focuses on optimizing a non-permutation flowshop. There are different skill levels considered for labor and the setup times on machines are sequence-dependent. Jobs are allowed to skip one or more stages in the flowshop. Job release and machine availability times are considered to be dynamic. The problem is solved in two layers. The outer layer is a search algorithm to find the schedule of jobs on the machine (traditional flowshop scheduling problem) and the inner layer is a three-step heuristic to find a schedule of jobs on labor in accordance to the machine schedule. Three different search algorithms are developed to solve the proposed NP-hard problem. First algorithm can solve a permutation flowshop while the other two are developed to solve a non-permutation flowshop. The comparison between the optimal solution and the search algorithms in small examples shows a good performance of the algorithms with an average deviation of only 2.00%. An experimental design analyzes the effectiveness and efficiency of the algorithms statistically. The results show that non-permutation algorithms perform better than the permutation algorithm, although the former are less efficient. The effectiveness and efficiency in all three algorithms have an inverse relation. To the best of our knowledge, this research is the first of its kind to provide a comprehensive mathematical model for dual resource flowshop scheduling problem.     

A Truncated Sum of Processing‐Times–Based Learning Model for a Two‐Machine Flowshop Scheduling Problem

Scheduling with learning effects has gained increasing attention in recent years. A well‐known learning model is called “sum‐of‐processing‐times‐based learning” in which the actual processing time of a job is a nonincreasing function of the jobs already processed. However, the actual processing time of a given job drops to zero precipitously when the normal job processing times are large. Moreover, the concept of learning process is relatively unexplored in a flowshop environment. Motivated by these observations, this article addresses a two‐machine flowshop problem with a truncated learning effect. The objective is to find an optimal schedule to minimize the total completion time. First, a branch‐and‐bound algorithm incorporating with a dominance property and four lower bounds is developed to derive the optimal solution. Then three simulated annealing algorithms are also proposed for near‐optimal solution. The experimental results indicated that the branch‐and‐bound algorithm can solve instances up to 18 jobs, and the proposed simulated annealing algorithm performs well in item of CPU time and error percentage. © 2011 Wiley Periodicals, Inc.     

Heuristic algorithms for two-machine flowshop with availability constraints

The majority of the scheduling studies carry a common assumption that machines are available all the time. However, machines may not always be available in the scheduling period due to breakdown or preventive maintenance. Taking preventive maintenance activity into consideration, we dealt with the two-machine flowshop scheduling problem with makespan objective. The preventive maintenance policy in this paper was dependent on the number of finished jobs. The integer programming model was proposed. We combined two recent constructive heuristics, HI algorithm and H algorithm, with Johnson’s algorithm, and named the combined heuristic H&J algorithm. We also developed a constructive heuristic, HD, with time complexities O(n²). Based on the difference in job processing times on two machines, both H&J and HD showed good performance, and the latter was slightly better. The HD algorithm was able to obtain the optimality in 98.88% of cases. We also employed the branch and bound (B&B) algorithm to obtain the optimum. With a good upper bound and a modified lower bound, the proposed B&B algorithm performed significantly effectively.     

Scheduling in a two-machine flowshop for the minimization of the mean absolute deviation from a common due date

This paper addresses the minimization of the mean absolute deviation from a common due date in a two-machine flowshop scheduling problem. We present heuristics that use an algorithm, based on proposed properties, which obtains an optimal schedule for a given job sequence. A new set of benchmark problems is presented with the purpose of evaluating the heuristics. Computational experiments show that the developed heuristics outperform results found in the literature for problems up to 500 jobs.     

An approximation scheme for two-machine flowshop scheduling with setup times and an availability constraint

This paper studies the two-machine permutation flowshop scheduling problem with anticipatory setup times and an availability constraint imposed only on the first machine. The objective is to minimize the makespan. Under the assumption that interrupted jobs can resume their operations, we present a polynomial-time approximation scheme for this problem.     

Heuristics for two-machine no-wait flowshop scheduling with an availability constraint

In this paper we study the two-machine no-wait flowshop problem with an availability constraint. The problem has been shown to be NP-hard, and some heuristics with a worst-case error bound of 2 have been developed for it. We provide two improved heuristics for the problem, and show that each has a worst-case error bound of 5/3.     

A two-machine flowshop problem with processing time-dependent buffer constraints—An application in multimedia presentations

To have a quality multimedia presentation through networks, its presentation lag needs to be controlled. One way to reduce the lag is to prefetch the media objects before their due dates. This paper explores techniques for optimizing the object sequence in a prefetch-enabled TV-like presentation. An optimal solution is the one with which the presentation lag is minimized. We formulate the problem into a two-machine flowshop scheduling problem with a single chain precedence constraint and a player-side buffer constraint. The player-side buffer is “processing time-dependent” and distinguished from the conventional item-based intermediate buffer constraints discussed in previous flowshop studies. We prove the problem to be strongly NP-hard. A branch and bound algorithm equipped with four lower bounds and an NEH-based upper bound is developed. The simulation results show that the average gaps between the overall lower bounds and the NEH-based upper bound are less than 3% for problems with a large buffer size, and less than 13% for problems with a small buffer size and high density of precedence constraints. For applications where the media objects are delivered through extremely busy servers with which only very restricted CPU resources can be allocated for computation, the CDS-based algorithm provides better sequences than the NEH-based algorithm.     

Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups

This paper focuses on minimizing the total completion time in two-machine group scheduling problems with sequence-dependent setups that are typically found in discrete parts manufacturing. As the problem is characterized as strongly NP-hard, three search algorithms based on tabu search are developed for solving industry-size scheduling problems. Four different lower bounding mechanisms are developed to identify a lower bound for all problems attempted, and the largest of the four is aptly used in the evaluation of the percentage deviation of the search algorithms to assess their efficacy. The problem sizes are classified as small, medium and large, and to accommodate the variability that might exist in the sequence-dependent setup times on both machines, three different scenarios are considered. Such finer levels of classification have resulted in the generation of nine different categories of problem instances, thus facilitating the performance of a very detailed statistical experimental design to assess the efficacy and efficiency of the three search algorithms. The search algorithm based on long-term memory with maximal frequencies either recorded a statistically better makespan or one that is indifferent when compared with the other two with all three scenarios and problem sizes. Hence, it is recommended for solving the research problem. Under the three scenarios, the average percentage deviation for all sizes of problem instances solved has been remarkably low. In particular, a mathematical programming based lower bounding mechanism, which focuses on converting (reducing) the original sequence-dependent group scheduling problem with several jobs in each group to a sequence-dependent job scheduling problem, has served well in identifying a high quality lower bound for the original problem, making it possible to evaluate a lower average percentage deviation for the search algorithm. Also, a 16–17-fold reduction in average computation time for solving a large problem instance with the recommended search algorithm compared with identifying just the lower bound of (not solving) the same instance by the mathematical programming based mechanism speaks strongly in favor of the search algorithm for solving industry-size group scheduling problems.     

Stochastic proportionate flowshop scheduling with setups

This paper addresses the problem of scheduling n jobs on a proportionate two-machine flowshop where the machines are subject to random breakdowns and setup times are considered separate from processing times. The considered performance measure is makespan. Sequences that minimize makespan with probability 1 are obtained when the first or the second machine is subject to random breakdowns without making any assumptions about downtime distributions or counting processes. It is assumed that the processing and setup times on one machine dominate the corresponding times on the other machine. In the case that processing and setup times on the first and second machines are proportionate, it is shown that the longest processing time (LPT) rule gives an optimal solution when only the first machine is subject to breakdowns, while the shortest processing time (SPT) rule yields an optimal solution when only the second machine suffers breakdowns.     

A branch-and-bound algorithm for single machine scheduling with quadratic earliness and tardiness penalties

This paper considers the problem of scheduling a single machine, in which the objective function is to minimize the weighted quadratic earliness and tardiness penalties and no machine idle time is allowed. We develop a branch and bound algorithm involving the implementation of lower and upper bounding procedures as well as some dominance rules. The lower bound is designed based on a lagrangian relaxation method and the upper bound includes two phases, one for constructing initial schedules and the other for improving them. Computational experiments on a set of randomly generated instances show that one of the proposed heuristics, used as an upper bound, has an average gap less than 1.3% for instances optimally solved. The results indicate that both the lower and upper bounds are very tight and the branch-and-bound algorithm is the first algorithm that is able to optimally solve problems with up to 30 jobs in a reasonable amount of time.