Minimizing total weighted completion time when scheduling orders in a flexible environment with uniform machines

We consider the scheduling of orders in an environment with m uniform machines in parallel. Each order requests certain amounts of k different product types. Each product type can be produced by any one of the m machines. No setup is required if a machine switches over from one product type to another. Different product types intended for the same order can be produced at the same time (concurrently) on different machines. Each order is released at time zero and has a positive weight. Preemptions are allowed. The completion time of an order is the finish time of the product type that is completed last for that order. The objective is to minimize the total weighted completion time. We propose heuristics for the non-preemptive as well as the preemptive case and obtain worst case bounds that are a function of the number of machines as well as the differences in the speeds of the machines. Even though the worst-case bounds we showed for the two heuristics are not very tight, our experimental results show that they yield solutions that are very close to optimal.     

New simple constructive heuristic algorithms for minimizing total flow-time in the permutation flowshop scheduling problem

This paper develops a set of new simple constructive heuristic algorithms to minimize total flow-time for an $n$-jobs×$m$-machines permutation flowshop scheduling problem. We first propose a new iterative algorithm based on the best existing simple heuristic algorithm, and then integrate new indicator variables for weighting jobs into this algorithm. We also propose new decision criteria to select the best partial sequence in each iteration of our algorithm. A comprehensive numerical experiment reveals that our modifications and extensions improve the effectiveness of the best existing simple heuristic without affecting its computational efficiency.     

Approximation algorithms for multi-agent scheduling to minimize total weighted completion time

We consider a multi-agent scheduling problem on a single machine in which each agent is responsible for his own set of jobs and wishes to minimize the total weighted completion time of his own set of jobs. It is known that the unweighted problem with two agents is NP-hard in the ordinary sense. For this case, we can reduce our problem to a Multi-Objective Shortest-Path (MOSP) problem and this reduction leads to several results including Fully Polynomial Time Approximation Schemes (FPTAS). We also provide an efficient approximation algorithm with a reasonably good worst-case ratio.     

Efficient heuristic algorithms for the blocking flow shop scheduling problem with total flow time minimization

This paper proposes two constructive heuristics, i.e. HPF1 and HPF2, for the blocking flow shop problem in order to minimize the total flow time. They differ mainly in the criterion used to select the first job in the sequence since, as it is shown, its contribution to the total flow time is not negligible. Both procedures were combined with the insertion phase of NEH to improve the sequence. However, as the insertion procedure does not always improve the solution, in the resulting heuristics, named NHPF1 and NHPF2, the sequence was evaluated before and after the insertion to keep the best of both solutions. The structure of these heuristics was used in Greedy Randomized Adaptive Search Procedures (GRASP) with variable neighborhood search in the improvement phase to generate greedy randomized solutions. The performance of the constructive heuristics and of the proposed GRASPs was evaluated against other heuristics from the literature. Our computational analysis showed that the presented heuristics are very competitive and able to improve 68 out of 120 best known solutions of Taillard’s instances for the blocking flow shop scheduling problem with the total flow time criterion.     

Three scheduling problems with deteriorating jobs to minimize the total completion time

In this paper, three scheduling problems with deteriorating jobs to minimize the total completion time on a single machine are investigated. By a deteriorating job, we mean that the processing time of the job is a function of its execution start time. The three problems correspond to three different decreasing linear functions, whose increasing counterparts have been studied in the literature. Some basic properties of the three problems are proved. Based on these properties, two of the problems are solved in O(nlogn) time, where n is the number of jobs. A pseudopolynomial time algorithm is constructed to solve the third problem using dynamic programming. Finally, a comparison between the problems with job processing times being decreasing and increasing linear functions of their start times is presented, which shows that the decreasing and increasing linear models of job processing times seem to be closely related to each other.     

A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective

In this paper we consider the job shop scheduling problem with total weighted tardiness objective (JSPTWT). This objective reflects the goal to achieve a high service level which is of increasing importance in many branches of industry. The paper concentrates on a class of baseline heuristics for this problem, known as neighborhood search techniques. An approach based on disjunctive graphs is developed to capture the general structure of neighborhoods for the JSPTWT. Existing as well as newly designed neighborhoods are formulated and analyzed. The performance and search ability of the operators (as well as combinations thereof) are compared in a computational study. Although no dominant operator is identified, a transpose-based perturbation on multiple machines turns out as a promising choice if applied as the only operator. Combining operators improves the schedule quality only slightly. But, the implementation of operators within a meta-heuristic enables to produce a higher schedule quality. A structural classification of neighborhood operators and some new analytical results are presented as well.     

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.     

Coupling Genetic Local Search and Recovering Beam Search algorithms for minimizing the total completion time in the single machine scheduling problem subject to release dates

In this paper we consider the well-known single machine scheduling problem with release dates and minimization of the total job completion time. For solving this problem, denoted by 1|r_j|∑C_j, we provide a new metaheuristic which is an extension of the so-called filtered beam search proposed by Ow and Morton [30]. This metaheuristic, referred to as a Genetic Recovering Beam Search (GRBS), takes advantages of a Genetic Local Search (GLS) algorithm and a Recovering Beam Search (RBS) in order to efficiently explore the solution space. In this paper we present the GRBS framework and its application to the 1|r_j|∑C_j problem. Computational results show that it consistently yields optimal or near-optimal solutions and that it provides interesting results by comparison to GLS and RBS algorithms. Moreover, these results highlight that the proposed algorithm outperforms the state-of-the-art heuristics.     

Minimizing total completion time for re-entrant flow shop scheduling problems

In this paper, we study re-entrant flow shop scheduling problems with the objective of minimizing total completion time. In a re-entrant scheduling problem, jobs may visit some machines more than once for processing. The problem is NP-hard even for machine number m=2. A heuristic algorithm is presented to solve the problem, in which an effective k-insertion technique is introduced as the improvement strategy in iterations. Computational experiments and analyses are performed to give guidelines of choosing parameters in the algorithm. We also provide a lower bound for the total completion time of the optimal solution when there are only two machines. Objective function values of the heuristic solutions are compared with the lower bounds to evaluate the efficiency of the algorithm. For randomly generated instances, the results show that the given heuristic algorithm generates solutions with total completion times within 1.2 times of the lower bounds in most of the cases.     

Single machine scheduling problem with interval processing times to minimize mean weighted completion time

The single resource scheduling problem is commonly applicable in practice not only when there is a single resource but also in some multiple-resource production systems where only one of the resources is bottle neck. Thus, the single resource (machine) scheduling problem has been widely addressed in the scheduling literature. In this paper, the single machine scheduling problem with uncertain and interval processing times is addressed. The objective is to minimize mean weighted completion time. The problem has been addressed in the literature and efficient heuristics have been presented. In this paper, some new polynomial time heuristics, utilizing the bounds of processing times, are proposed. The proposed and existing heuristics are compared by extensive computational experiments. The conducted experiments include a generalized simulation environment and several additional representative distributions in addition to the restricted experiments used in the literature. The results indicate that the proposed heuristics perform significantly better than the existing heuristics. Specifically, the best performing proposed heuristic reduces the error of the best existing heuristic in the literature by more than 75% while the computational time of the best performing proposed heuristic is less than that of the best existing heuristic. Moreover, the absolute error of the best performing heuristic is only about 1% of the optimal solution. Having a very small absolute error along with a negligible computational time indicates the superiority of the proposed heuristics.     

A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: Weighted mean completion time and weighted mean tardiness

This paper investigates a novel multi-objective model for a no-wait flow shop scheduling problem that minimizes both the weighted mean completion time and weighted mean tardiness . Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using traditional approaches and optimization tools is extremely difficult. This paper presents a new hybrid multi-objective algorithm based on the features of a biological immune system (IS) and bacterial optimization (BO) to find Pareto optimal solutions for the given problem. To validate the performance of the proposed hybrid multi-objective immune algorithm (HMOIA) in terms of solution quality and diversity level, various test problems are examined. Further, the efficiency of the proposed algorithm, based on various metrics, is compared against five prominent multi-objective evolutionary algorithms: PS-NC GA, NSGA-II, SPEA-II, MOIA, and MISA. Our computational results suggest that our proposed HMOIA outperforms the five foregoing algorithms, especially for large-sized problems.     

Exact and parallel metaheuristic algorithms for the single processor total weighted completion time scheduling problem with the sum-of-processing-time based models

In this paper, the single processor scheduling problem to minimize the total weighted completion times is analysed, where the processing times of jobs are described by functions dependent on the sum of the normal processing times of previously processed jobs, which can model learning or aging (deteriorating) effects. We construct the exact pseudopolynomial time algorithm based on the dynamic programming, which solves the problem, where the processing time of each job is described by an arbitrary stepwise function. Moreover, the parallel metaheuristic algorithms are provided for the general version of the problem with arbitrary sum-of-processing time based models. The efficiency of the proposed algorithms is evaluated during numerical analysis.     

Optimizing blocking flow shop scheduling problem with total completion time criterion

The blocking flow shop scheduling problem has found many applications in manufacturing systems. There are a few exact methods for solving this problem with different criteria. In this paper, efforts will be made to optimize the total completion time criterion for this problem. We present two mixed binary integer programming models, one of which is based on the departure times of jobs from machines, and the other is based on the idle and blocking times of jobs. An initial upper bound generator and some lower bounds and dominance rules are also developed to be used in a branch and bound algorithm. The algorithm solves 17 instances of the Taillard's benchmark problem set in less than 20 min.     

Integrated order acceptance and supply chain scheduling problem with supplier selection and due date assignment

The importance, benefits, and impact of integration of decisions within supply chains have long been investigated by many researchers. Order acceptance and supplier selection are two of the most critical decisions for supply chain managers. Throughout the process of order acceptance, a manufacturer has to decide which orders to be accepted and processed and based on the accepted orders, the volume of required raw material is determined. On the other hand, a manufacturer aims to choose one or several suppliers among all possible choices to provide sufficient raw material for the accepted orders, subject to different criteria such as list price, transportation cost, etc. This paper addresses an integrated framework for profit maximization in an integrated supplier selection, order acceptance and scheduling problem in a single-machine environment with multiple customers. There is substantial literature on the problems of supplier selection and order acceptance; however, to the best of our knowledge, this paper is the first research that integrates these essential decisions in the form of a mathematical model to maximize the total profit. The problem is NP-hard in nature; therefore, solving to optimality is not practically possible for problems with medium and large size. For that purpose, we developed a Heuristic Algorithm (HA) to solve the problem above in a reasonable time, with proper accuracy. Results from this heuristic algorithm are compared with that of a commercial solver (GAMS) and the well-known Genetic Algorithm (GA) and Variable Neighborhood Search (VNS). Computational experiments demonstrate that the developed heuristic algorithm is more efficient in comparison with other tested methods.     

Improving the delivery efficiency of the customer order scheduling problem in a job shop

The focus of this paper is customer order scheduling (COS) problem, where each order consists of a set of jobs that must be shipped as one batch at the same time. In COS each job is part of a customer order and the make-up of the jobs in the order are pre-specified. Most of the existing research deals with COS in a single machine or in a parallel machine shop for developing an optimal solution. COS is common in a normal job shop, and the more complex the shop, the more complex the scheduling. Most existing research has focused on trying to reduce the completion time of the batch. That is, the focus is only on the point in time the last job is finished, while ignoring the actual duration of the jobs within the same order. The longer it takes to complete all the jobs within an order the more it increases the stock of finished goods and the more it deteriorates the efficiency of the logistics and the supply chain management.A new dispatching rule, referred to as Minimum Flow Time Variation (MFV), has been proposed for COS in a normal job shop, in order to reduce the total time it takes to complete all jobs within the same order. That is, the individual completion times of all jobs for the same customer order will be controlled in order to improve the shipping performance. In the simulation test and statistical analysis, the level of work in process (WIP) under the MFV rule in the finished goods warehouse is reduced by more than 70% compared to any other method. The MFV method will efficiently reduce the stock level of finished goods, and controls the waiting time required before they can be shipped. Depending on the environmental factors, the performance of our proposed method will become increasingly significant the more complex the system.     

Approximation algorithms for shop scheduling problems with minsum objective: A correction

We present a correction to the paper, “Approximation algorithms for shop scheduling problems with minsum objective” (Journal of Scheduling 2002; 5:287–305) by Queyranne and Sviridenko. This correction provides a correct derivation of its 2eρ approximation result. Wenhua Li and Jinjiang Yuan: Project supported by NNSFC (Grant 10371112) and NSFHN (Grant 0411011200). Maurice Queyranne: Supported by research grants from NSERC, the Natural Sciences and Engineering Research Council of Canada.     

Heuristic algorithms for lotsize scheduling with application in the tobacco industry

We investigate a production planning problem which appears in many industries. We present an example from the tobacco industry. The basic question is how tasks of different types can be scheduled on machines in lots such that the number of changeovers is minimized. These changeovers occur if two tasks of different types are scheduled in sequence on a machine. We analyze the problem in detail and present heuristics for the single and multiple machine case. We evaluate these heuristics and give recommendations for their application to serial production systems.