Inverse scheduling with maximum lateness objective

We study a range of counterparts of the single-machine scheduling problem with the maximum lateness criterion that arise in the context of inverse optimization. While in the forward scheduling problem all parameters are given and the objective is to find the optimal job sequence for which the value of the maximum lateness is minimum, in inverse scheduling the exact values of processing times or due dates are unknown, and they should be determined so that a prespecified solution becomes optimal. We perform a fairly complete classification of the corresponding inverse models under different types of norms that measure the deviation of adjusted parameters from their given estimates.     

A two-machine flowshop makespan scheduling problem with deteriorating jobs

In traditional scheduling problems, the job processing times are assumed to be known and fixed from the first job to be processed to the last job to be completed. However, in many realistic situations, a job will consume more time than it would have consumed if it had begun earlier. This phenomenon is known as deteriorating jobs. In the science literature, the deteriorating job scheduling problems are relatively unexplored in the flowshop settings. In this paper, we study a two-machine flowshop makespan scheduling problem in which job processing times vary as time passes, i.e. they are assumed as increasing functions of their starting times. First, an exact algorithm is established to solve most of the problems of up to 32 jobs in a reasonable amount of time. Then, three heuristic algorithms are provided to derive the near-optimal solutions. A simulation study is conducted to evaluate the performances of the proposed algorithms. In addition, the impact of the deterioration rate is also investigated.     

Quantity-based buffer-constrained two-machine flowshop problem: active and passive prefetch models for multimedia applications

Conventional studies on buffer-constrained flowshop scheduling problems have considered applications with a limitation on the number of jobs that are allowed in the intermediate storage buffer before flowing to the next machine. The study in Lin et al. (Comput. Oper. Res. 36(4):1158?C1175, 2008a) considered a two-machine flowshop problem with ??processing time-dependent?? buffer constraints for multimedia applications. A???passive?? prefetch model (the PP-problem), in which the download process is suspended unless the buffer is sufficient for keeping an incoming media object, was applied in Lin et al. (Comput. Oper. Res. 36(4):1158?C1175, 2008a). This study further considers an ??active?? prefetch model (the AP-problem) that exploits the unoccupied buffer space by advancing the download of the incoming object by a computed maximal duration that possibly does not cause a buffer overflow. We obtain new complexity results for both problems. This study also proposes a new lower bound which improves the branch and bound algorithm presented in Lin et al. (Comput. Oper. Res. 36(4):1158?C1175, 2008a). For the PP-problem, compared to the lower bounds developed in Lin et al. (Comput. Oper. Res. 36(4):1158?C1175, 2008a), on average, the results of the simulation experiments show that the proposed new lower bound cuts about 38% of the nodes and 32% of the execution time for searching the optimal solutions.     

A note on reverse scheduling with maximum lateness objective

The inverse and reverse counterparts of the single-machine scheduling problem $1||L_{\max }$ are studied in [2], in which the complexity classification is provided for various combinations of adjustable parameters (due dates and processing times) and for five different types of norm: $\ell _{1},\ell _{2},\ell _{\infty },\ell _{H}^{\Sigma } $ , and $\ell _{H}^{\max }$ . It appears that the $O(n^{2})$ -time algorithm for the reverse problem with adjustable due dates contains a flaw. In this note, we present the structural properties of the reverse model, establishing a link with the forward scheduling problem with due dates and deadlines. For the four norms $\ell _{1},\ell _{\infty },\ell _{H}^{\Sigma }$ , and $ \ell _{H}^{\max }$ , the complexity results are derived based on the properties of the corresponding forward problems, while the case of the norm $\ell _{2}$ is treated separately. As a by-product, we resolve an open question on the complexity of problem $1||\sum \alpha _{j}T_{j}^{2}$ .     

A two-machine flowshop scheduling problem with a separated maintenance constraint

This paper considers a two-machine flowshop scheduling problem with a separated maintenance constraint. This means that the machine may not always be available during the scheduling period. It needs a constant time to maintain the machine after completing a fixed number of jobs at most. The objective is to find the optimal job combinations and the optimal job schedule such that the makespan is minimized. The proposed problem has some practical applications, for example, in electroplating process, the electrolytic cell needs to be cleaned and made up a deficiency of medicine. In this paper, we propose a heuristic algorithm to solve this problem. Some polynomially solvable cases and computational experiments are also provided.     

Heuristic algorithms for solving the maximum lateness scheduling problem with learning considerations

In many situations, a worker’s ability improves as a result of repeating the same or similar task; this phenomenon is known as the “learning effect”. In this paper, the learning effect is considered in a single-machine maximum lateness minimization problem. A branch-and-bound algorithm, incorporating several dominance properties, is provided to derive the optimal solution. In addition, two heuristic algorithms are proposed for this problem. The first one is based on the earliest due date (EDD) rule and a pairwise neighborhood search. The second one is based on the simulated annealing (SA) approach. Our computational results show that the SA algorithm is surprisingly accurate for a small to medium number of jobs. Moreover, the SA algorithm outperforms the traditional heuristic algorithm in terms of quality and execution time for a large number of jobs.     

A hybrid Electromagnetism-like Mechanism/tabu search procedure for the single machine scheduling problem with a maximum lateness objective

This paper presents a hybrid meta-heuristic search procedure to solve the well-known single machine scheduling problem to minimize the maximum lateness over all jobs, where precedence relations may exist between some of the jobs. The hybridization consists of a well-designed balance between the principles borrowed from an Electromagnetism-like Mechanism algorithm and the characteristics used in a tabu search procedure. The Electromagnetism-like Mechanism (EM) algorithm follows a search pattern based on the theory of physics to simulate attraction and repulsion of solutions in order to move towards more promising solutions. The well-known tabu search enhances the performance of a local search method by using memory structures by prohibiting visited solutions during a certain time of the search process. The hybridization of both algorithms results in an important trade-off between intensification and diversification strategies. These strategies will be discussed in detail. To that purpose, a new set of data instances is used to compare different elements of the hybrid search procedure and to validate the performance of the algorithm.     

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 generalized two-machine flowshop scheduling problem with processing time linearly dependent on job waiting-time

We consider a two-machine flowshop scheduling problem where the processing times are linearly dependent on the waiting times of the jobs. The objective is to minimize the makespan. A 0–1 mixed integer program and a heuristic algorithm are proposed. Some cases solved in polynomial time and computational experiments are also provided.     

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.     

The two-machine flowshop no-wait scheduling problem with a single server to minimize the total completion time

This work studies the scheduling problem where a set of jobs are available for processing in a no-wait and separate setup two-machine flow shop system with a single server. The no-wait constraint requires that the operations of a job have to be processed continuously without waiting between two machines. The setup time is incurred and attended by a single sever which can perform one setup at a time. The performance measure considered is the total completion time. The problem is strongly NP-hard. Optimal solutions for several restricted cases and some properties for general case are proposed. Both the heuristic and the branch and bound algorithms are established to tackle the problem. Computational experiments indicate that the heuristic and the branch and bound algorithm are superior to the existing ones in term of solution quality and number of branching nodes, respectively.     

A heuristic-based genetic algorithm for the two-machine flowshop scheduling with learning consideration

In scheduling problems, the learning phenomenon is often seen in some practical applications such as in the processing of certain chemicals in oil refineries and in the steel plates or bars produced by a foundry. A review of the literature reveals that most researchers paid more attention to the scheduling with both the single-machine settings and the learning without a bound. This is at odds with reality and thereby highlights the importance of addressing the issue by different approaches. This paper tackles the issue by considering a two-machine flowshop problem with a truncated learning consideration where the objective function is to minimize the makespan. In order to solve the proposed model, a branch-and-bound algorithm is first developed for the optimal solution. Then four genetic heuristic-based algorithms are proposed for the near-optimal solution. In addition, the experimental results of all proposed algorithms are also provided.     

Heuristics for a two-stage assembly flowshop with bicriteria of maximum lateness and makespan

We consider a two-stage assembly flowshop scheduling problem with the objective of minimizing a weighted sum of makespan and maximum lateness. The problem is known to be NP-hard, and therefore, we propose heuristics to solve the problem. The proposed heuristics are Tabu search (Tabu), particle swarm optimization (PSO), and self-adaptive differential evolution (SDE). An extensive computational experiment is conducted to compare performances of the proposed heuristics. The computational experiment reveals that both PSO and SDE are much superior to Tabu. Moreover, it is statistically shown that PSO performs better than SDE. The computation times of both PSO and SDE are close to each other and they are less than 40 and 45 s, respectively, for the largest size problem considered.     

Two-agent two-machine flowshop scheduling with learning effects to minimize the total completion time

We study a two-agent scheduling problem in a two-machine permutation flowshop with learning effects. The objective is to minimize the total completion time of the jobs from one agent, given that the maximum tardiness of the jobs from the other agent cannot exceed a bound. We provide a branch-and-bound algorithm for the problem. In addition, we present several genetic algorithms to obtain near-optimal solutions. Computational results indicate that the algorithms perform well in either solving the problem or efficiently generating near-optimal solutions.     

Efficient non-population-based algorithms for the permutation flowshop scheduling problem with makespan minimisation subject to a maximum tardiness

This paper focuses on the problem of scheduling jobs in a permutation flowshop with the objective of makespan minimisation subject to a maximum allowed tardiness for the jobs, a problem that combines two desirable manufacturing objectives related to machine utilisation and to customer satisfaction. Although several approximate algorithms have been proposed for this NP-hard problem, none of them can use the excellent speed-up method by Taillard (1990) [22] for makespan minimisation due to the special structure of the problem under consideration. In this paper, several properties of the problem are defined in order to be able to partly apply Taillard׳s acceleration. This mechanism, together with a novel feasible tabu local search method, allows us to further exploit the structure of solutions of the problem, and are incorporated in two proposed algorithms: a bounded-insertion-based constructive heuristic and an advanced non-population-based algorithm. These algorithms are compared with state-of-the-art algorithms under the same computer conditions. The results show that both algorithms improve existing ones and therefore, constitute the new state-of-art approximate solution procedures for the problem.     

A grasp algorithm for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness

In this paper we address the problem of minimizing the weighted sum of makespan and maximum tardiness in an m-machine flow shop environment. This is a NP-hard problem in the strong sense. An attempt has been made to solve this problem using a metaheuristic called Greedy Randomized Adaptive Search Procedure (GRASP). GRASP is a competitive algorithm and is a meta-heuristic for solving combinatorial optimization problems. We have customized the basic concepts of GRASP algorithm to solve a bicriteria flow shop problem and a new algorithm named B-GRASP (Bicriteria GRASP algorithm) is proposed. The new proposed algorithm is evaluated using benchmark problems taken from Taillard and compared with the existing simulated annealing based heuristic developed by Chakravarthy and Rajendran. Computational experiments indicate that the proposed algorithm is much better than the existing one in all cases.     

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.