Minimizing mean absolute deviation of completion time about a common due window subject to maximum tardiness for a single machine

This study deals with the problem of scheduling jobs on a single machine to minimize the mean absolute deviation of the job completion time about a large common due window subject to the maximum tardiness constraint. Using the well-known three-field notation, the problem is identified as MAD/large DueWindow/T_max. The common due window is set to be large enough to allow idle time prior to the beginning of a schedule to investigate the effect of the T_max constraint. Penalties arise if a job is completed outside the due window. A branch and bound algorithm and a heuristic are proposed. Many properties of the solutions and precedence relationships are identified. Our computational results reveal that the branch and bound algorithm is capable of solving problems of up to 50 jobs and the heuristic algorithm yields approximate solutions that are very close to the exact solution.     

Heuristics for operational fixed job scheduling problems with working and spread time constraints

Operational fixed job scheduling problems select a set of jobs having fixed ready and processing times and schedule the selected jobs on parallel machines so as to maximize the total weight. In this study, we consider working time and spread time constrained versions of the operational fixed job scheduling problems. The working time constraints limit the total processing load on each machine. The spread time constraints limit the time between the start of the first job and the finish of the last job on each machine. For the working time constrained problem, we present a filtered beam search algorithm that evaluates the promising nodes of the branch and bound tree. For the spread time constrained problem we propose a two phase algorithm that defines the promising sets for the first jobs and finds a solution for each promising set. The results of our computational tests reveal that our heuristic algorithms perform very well in terms of both solution quality and time.     

Order acceptance and scheduling in a two-machine flowshop

We study the order acceptance and scheduling problem in a two-machine flowshop. The firm receives a pool of orders before a planning period, each of which is characterized by revenue, processing times on machines 1 and 2, a due date, and a tardiness penalty. The firm seeks to decide on the orders to accept and schedule the accepted orders so as to maximize the total net revenue. We formulate the problem as mixed-integer linear programming models, and develop a heuristic and a branch-and-bound (B&B) algorithm based on some derived dominance rules and relaxation techniques. We assess the performance of the B&B algorithm and the heuristic via computational experiments. The computational results show that the B&B algorithm can solve problem instances with up to 20 jobs within a reasonable time while the heuristic is efficient in approximately solving large instances of the problem.     

Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem

We consider the multistage hybrid flowshop scheduling problem, in which each stage consists of parallel identical machines. The problem is to determine a schedule that minimizes the makespan for a given set of jobs over a finite planning horizon. Since this problem class is NP-hard in the strong sense, there seems to be no escape from appealing to heuristic procedures to achieve near-optimal solutions to real life problems. First, a series of new global lower bounds to be used to estimate the minimum makespan are derived. Then, two new metaheuristic algorithms first sequence and then allocate jobs to machines based on a particular partition of the shop. The optimization procedure is based on simulated annealing and the variable-depth search. Computational experiments show the efficiency of the proposed procedures.     

Particle swarm optimization with cocktail decoding method for hybrid flow shop scheduling problems with multiprocessor tasks

This paper addresses the problem of multiprocessor task-scheduling in a hybrid flow shop (HFS) problem to minimize the makespan. Due to the complex nature of an HFS problem, it is decomposed into the following two sequential decision problems: determining the job permutation in stage 1, followed by a decoding method to assign jobs into each machine in subsequent stages when designing a heuristic algorithm. The decoding method plays a pivotal role for improving the solution quality of any algorithm for the HFS problem. However, the majority of existing algorithms ignores the problem and is only concerned with the first decision problem. This study emphasizes the importance of the decoding method via a small test, and searches for a number of solid decoding methods that can be incorporated into the cocktail decoding method. Then, this study develops a particle swarm optimization (PSO) algorithm that can be combined with the cocktail decoding method. In the PSO, a variety of job sequences are generated using the PSO procedure in stage 1, and the cocktail decoding method is used to assign the jobs to machines in sequential stages. Moreover, a modified lower bound is introduced. Computational results show that the proposed lower bound is competitive, and with the help of the cocktail decoding method, the proposed PSO, and even the adoption of a standard PSO framework, significantly outperforms the majority of existing algorithms in terms of quality of solutions, especially for large problems.     

Scheduling a single batch processing machine with arbitrary job sizes and incompatible job families

Motivated by a bottleneck operation in a multi-layer ceramic capacitor production line, we study a scheduling problem of batch processing machine in which a number of jobs are processed simultaneously as a batch. The performance measures considered include makespan, total completion time, and total weighted completion time. We first present a new simple integer programming formulation for the problem, and using this formulation, one can easily find optimal solutions for small problems. However, since the problem is NP-hard and the size of a real problem is very large, we propose a number of heuristic algorithms and design a hybrid genetic algorithm to solve practical big-size problems in a reasonable computational time. To verify performance of the algorithms, we compare them with lower bounds for the problems. From the results of these computational experiments the heuristic algorithms including the genetic algorithm show different performances for the three problems.     

Scheduling jobs with values dependent on their completion times

The paper concerns two scheduling problems with job values and losses of job values (costs) dependent on job completion times. In the first problem, we consider scheduling jobs with stepwise values in parallel processor environment. In the stepwise value, there is given a number of moments at which the job value decreases and between them the job value is constant (thus, the value deteriorates over time). The maximized criterion is the total job value. We prove strong NP-hardness of a single processor case of the problem and construct a pseudo-polynomial time algorithm for a special case with fixed number of unrelated parallel processors and fixed number of common moments of job value changes. Additionally, for uniform and unrelated parallel processors we construct and experimentally test several heuristic algorithms based on the list strategy. The second problem is a single processor one with piecewise linear losses of job values (the loss increases over time). The minimized criterion is the total loss of job value. We prove strong NP-hardness of the problem and existence of a pseudo-polynomial time exact algorithm for its special case. We also construct some heuristic algorithms for this problem and verify experimentally their efficiency.     

A genetic algorithm based heuristic for two machine no-wait flowshop scheduling problems with class setup times that minimizes maximum lateness

Machine scheduling problem has been extensively studied by researchers for many decades in view of its numerous applications on solving practical problems. Due to the complexity of this class of scheduling problems, various approximation solution approaches have been presented in the literature. In this paper, we present a genetic algorithm (GA) based heuristic approach to solve the problem of two machine no-wait flowshop scheduling problems that the setup time on the machines is class dependent, and the objective is to minimize the maximum lateness of the jobs processed. This class of machine scheduling problems has many practical applications in manufacturing industry, such as metal refinery operations, food processing industry and chemical products production processes, in which no interruption between subsequent processes is allowed and the products can be grouped into families. Extensive computation experiments have been conducted to evaluate the effectiveness of the proposed algorithm. Results show the proposed methodology is suitable to be adopted for the development of an efficient scheduling plan for this class of problems in real life application.     

Non-permutation flowshop scheduling in a supply chain with sequence-dependent setup times

In this paper, we consider a flowshop scheduling problem with sequence-dependent setup times and a bicriteria objective to minimize the work-in-process inventory for the producer and to maximize the customers' service level. The use of a bicriteria objective is motivated by the fact that successful companies in today's environment not only try to minimize their own cost but also try to fulfill their customers' need. Two main approaches, permutation and non-permutation schedules, are considered in finding the optimal schedule for a flowshop. In permutation schedules the sequence of jobs remains the same on all machines whereas in non-permutation schedule, jobs can have different sequence on different machines. A linear mathematical model for solving the non-permutation flowshop is developed to comply with all of the operational constraints commonly encountered in the industry, including dynamic machine availabilities, dynamic job releases, and the possibility of jobs skipping one or more machines, should their operational requirements deem that it was necessary. As the model is shown to be NP-hard, a metasearch heuristic, employing a newly developed concept known as the Tabu search with embedded progressive perturbation (TSEPP) is developed to solve, in particular, industry-size problems efficiently. The effectiveness and efficiency of the search algorithm are assessed by comparing the search algorithmic solutions with that of the optimal solutions obtained from CPLEX in solvable small problem instances.     

Two-machine flow shop scheduling of polyurethane foam production

This paper studies a two-machine flow shop scheduling problem with a supporting precedence relation. The model originates from a real production context of a chemical factory that produces foam-rubber products. We extend the traditional two-machine flow shop by dividing the operations into two categories: supporting tasks and regular jobs. In the model, several different compositions of foam rubber can be mixed at the foam blooming stage, and products are processed at the manufacturing stage. Each job (product) on the second machine cannot start until its supporting tasks (parts) on the first machine are all finished and the second machine is not occupied. The objective is to find a schedule that minimizes the total job completion time. The studied problem is strongly NP-hard. In this paper, we propose a branch-and-bound algorithm incorporating a lower bound and two dominance rules. We also design a simple heuristic and an iterated local search (ILS) algorithm to derive approximate solutions. The performances of the proposed algorithms are examined through computational experiments.     

A note on constructive heuristics for the flowshop problem with blocking

This paper analyzes the minimization of the makespan criterion for the flowshop problem with blocking. In this environment, there are no buffers between successive machines, and therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. As the problem is NP-hard, a constructive heuristic that explores specific characteristics of the problem is developed. The small computational effort of such strategy, which is valuable in practical applications, is one of the reasons that motivated this study. The performance of a combination of the proposed method with existing ones is examined through a comparative study. The new methods outperform the NEH algorithm, currently the best constructive heuristic for this problem, in problems with up to 500 jobs and 20 machines.     

An efficient heuristic for medium-term planning in shampoo production

This paper presents a single machine problem which occurs in shampoo production at medium-term planning phase. The considered production plant is linked to subsidiary companies which are themselves linked to final customers. The aim is to answer subsidiary companies requests by keeping their stocks in a window defined by their safety stock and maximum inventory levels. After an introduction, we present a formal definition of the problem. Next, we present a two-phase heuristic algorithm: the first phase is based on a greedy algorithm and the second phase on the Goldberg and Tarjan algorithm for the minimum cost flow problem. Experimental testings close to industrial instances show that the heuristic performs very efficiently.     

A memetic algorithm for a multistage capacitated lot-sizing problem

We present a heuristic approach to solve a complex problem in production planning, the multistage lot-sizing problem with capacity constraints. It consists of determining the quantity to be produced in different periods in a planning horizon, such that an initially given demand forecast can be attained. We consider setup costs and setup times. Due the complexity to solve this problem, we developed methods based on evolutionary metaheuristics, more specifically a memetic algorithm. The proposed heuristics are evaluated using randomly generated instances and well-known examples in the literature.     

A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system

We analyze a two-machine flow-shop scheduling problem in which the job processing times are controllable by the allocation of resources to the job operations and the resources can be used in discrete quantities. We provide a bicriteria analysis of the problem where the first criterion is to maximize the weighted number of just-in-time jobs and the second criterion is to minimize the total resource consumption cost. We prove that although the problem is known to be NP-hard even for constant processing times, a pseudo-polynomial time algorithm for its solution exists. In addition, we show how the pseudo-polynomial time algorithm can be converted into a two-dimensional fully polynomial approximation scheme for finding an approximate Pareto solution.     

An improved algorithm and solution on an integrated production-inventory model in a three-layer supply chain

Ben-Daya et al. (2010) established a joint economic lot-sizing problem (JELP) for a three-layer supply chain with one supplier, one manufacturer, and multiple retailers, and then proposed a heuristic algorithm to obtain the integral values of four discrete variables in the JELP. In this paper, we first complement some shortcomings in Ben-Daya et al. (2010), and then propose a simpler improved alternative algorithm to obtain the four integral decision variables. The proposed algorithm provides not only less CPU time but also less total cost to operate than the algorithm by Ben-Daya et al. (2010). Furthermore, our proposed algorithm can solve certain problems, which cannot be solved by theirs. Finally, the solution obtained by the proposed algorithm is indeed a global optimal solution in each of all instances tested.     

Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective

This paper addresses the problem of scheduling a set of independent jobs on unrelated parallel machines with job sequence dependent setup times so as to minimize a weighted mean completion time. The study of the problem stemmed from a real service industry problem. This problem is at least NP-hard in the ordinary sense, even when there are only two identical machines with no setups. Seven heuristic algorithms are proposed and tested by simulation. The results and analysis of quite extensive computational experiments are reported and discussed. The findings through the computational results are presented. Whether this problem is strongly NP-hard is left as an open question.     

Supply chain scheduling and coordination with dual delivery modes and inventory storage cost

We study a two-echelon supply chain scheduling problem in which a manufacturer acquires supplies from an upstream supplier and processes orders from the downstream retailers. The supply chain sells a single short-life product in a single season. We consider the scenario where the manufacturer can only accept some of the orders from the retailers due to its supplier's common production time window and its own two common production and delivery time windows. The upstream supplier processes materials and delivers the semi-finished products to the manufacturer within its time window. Then the manufacturer further processes these products to produce finished products and delivers them to the retailers within its two time windows, where one window is for production and normal delivery, and the other is for production and express delivery. Having to store the materials before processing them, the supplier incurs a storage cost, which depends on the order size and storage time. The manufacturer pays the transportation cost for delivering the finished products to the retailers. Due to double marginalization, the performance of the supply chain is sub-optimal. We model the supply chain problem as a flow shop scheduling problem with multiple common time windows. We derive some dominance properties and establish some theorems that help solve the sequencing problems for the orders and eliminate the idle time among the orders. Based on these results, we develop fast pseudo-polynomial dynamic algorithms to optimally solve the problem. We prove that the problem is NP-hard in the ordinary sense only. We develop two practically relevant and robust methods for the supply chain to achieve optimal profit-making performance through channel coordination.     

A hybrid heuristic algorithm adopting both Boltzmann function and mutation operator for manufacturing cell formation problems

This study proposes a hybrid heuristic algorithm employing both the Boltzmann function from simulated annealing and the mutation operator from the genetic algorithm to explore the unvisited solution region and expedite the solution searching process for the cell formation problem, so that grouping efficacy is maximized. Test problems drawn from the literature are used to test the performance of the proposed heuristic algorithm. The comparative study shows that the proposed algorithm improves the best results found in the literature for 36% of the test problems in the case when singletons solutions are allowed.     

Resource management in software as a service using the knapsack problem model

This paper proposes a resource allocation model for “Software as a Service” systems that maximizes the service provider's revenues and the resource utilization under a heavy load. Employing the elasticity of virtualized infrastructures, the proposed model dictates that system resources must be fully exploited by incoming jobs, even if they do not satisfy their requirements completely. This yields a higher Service Level Agreement violation probability, which is mitigated by the assignment of more resources when these become available. The problem is deduced to the Fractional Knapsack problem and the heuristic solution is implemented in the frame of a SOA environment.     

A branch and bound algorithm for sub-contractor selection in agile manufacturing environment

Partnership and partner selection play a key role for “Opportunity Driven” project contractors in agile manufacturing environment. In this paper, we present an investigation on the partner selection problems with engineering projects. Firstly, the problem is described by a 0–1 integer programming with non-analytical objective function. It is proven that the partner selection problem is a type of earliness and tardiness production planning problems. By introducing the concepts of inefficient and ideal candidates, we propose the theory of solution space reduction which can efficiently reduce the complexity of the problem. Then, a branch and bound algorithm embedded project scheduling is developed to obtain the solution. The approach was demonstrated by the use of an experimental example drawn from a construction project of coal fire power station. The computational results have been found to be satisfactory.