Search

Most research studies in the batch process control problem are focused on optimizing system performance. The methods address the problem by minimizing a single criterion, such as cycle time and tardiness, or bi-criteria such as cycle time and tardiness, and earliness and tardiness. We demonstrate the utilization of the Stochastic Utility Evaluation (SUE) function approach to the performance of batch process systems using multiple criteria. Tri-criteria problem is used as an example to illustrate the use of the SUE function. That is, we explore how SUE function with stochastic information can be implemented to improve existing approaches to the batch process control problem. The simulation results demonstrate that strategies based on the SUE function perform better than existing strategies based on static utility values. [ABSTRACT FROM AUTHOR]

This paper considers the common due date assignment for single machine weighted earliness/tardiness scheduling problem with different earliness and tardiness weights for jobs where the objective is to minimize the cost of the sum of weighted earliness/tardiness and assignment common due date. The single machine common due date assignment problem where all jobs have the same earliness/tardiness weight has a polynomial-time algorithm to solve it optimally. Furthermore, some properties for the problem where the common due date is an input have been revealed by researchers in the literature. This paper proposes a heuristic algorithm for the problem using the revealed properties of similar problems' optimal solutions such as the V-shaped property and zero-start time of the machine. The experimental study of this paper shows that the proposed heuristic finds better solutions for the problems in a reasonable time than a commercial solver has when the problem size is increased. [ABSTRACT FROM AUTHOR]

Purpose: Scheduling of batch production and machine disruption are the two main challenges in manufacturing organizations. Due to the complexity of production processes, many industries try to group jobs according to family criteria and use a common setup time to process every family. Also, machine breakdown is an influential factor in the planning of production systems. In this paper, the problem of scheduling a single machine with family setup times and breakdowns is studied. It is assumed that there is a breakdown with an uncertain start time and duration based on the specified probability distribution functions during the planning horizon. The objective function of this problem is the sum of the expected maximum earliness and maximum tardiness. Design/methodology/approach: For the problem under study, a new mixed integer linear programming model has been developed. Due to the NP-hardness of the problem, a new branch and bound algorithm with the dominance rules and an efficient lower bound is presented for its optimal solving, which uses a new heuristic approach to achieve the upper bound. Findings: To evaluate the performance of the introduced algorithms, 2520 instances were designed and solved with the presented algorithms. The computational results indicated that 98% of the instances were optimally solved in the specified time limitation by the branch and bound algorithm, and the average percentage of deviation from the optimal solution in the proposed heuristic approach was less than 30%. The results demonstrated the efficiency of the proposed algorithms. Research limitations/implications: Considering the newness of the problem investigated in this paper, the proposed instances and algorithms can be used as a basis for evaluating other solution methodologies in future research studies. Also, considering other modes of machine failures such as scenario-based failures or re-scheduling the jobs to minimize the deviations of the actual schedule from the planned program, situations with more than one machine such as parallel machines, flow shops, and job shops, other objective functions related to scheduling such as maximum completion time or total completion time, as well as the development of other exact, heuristic or meta-heuristic algorithms are suggested as subjects for future study. Practical implications: The problem studied in this paper can be attractive and practical for manufacturing organizations. Industries such as automotive, ship and aircraft manufacturing, steel, telecommunication power supply manufacturing, electronic, computer processors, and all industries and systems that somehow deal with the batch production process and unexpected machine breakdowns, can benefit from the results of this research. Social implications: Because in this study, the starting and finishing times of machine breakdowns were predicted, by applying the results of this research, the production of defective products will be prevented when the machine breaks down, and this leads to the reduction of waste in the environment. Also, according to the objective function defined in the problem investigated in this article, the implication of the results of this research in production environments leads to the reduction of earliness and tardiness costs, which in turn increases the work efficiency of human resources and as a result, increases the job satisfaction. Originality/value: It seems no study has been conducted on the single machine scheduling problem with batch production, random breakdown, and the objective function of minimizing the sum of the expected maximum earliness and maximum tardiness of the jobs. Particularly, innovations of this paper are threefold: i) a new mixed integer linear programming model was developed for the problem; ii) a novel heuristic approach was proposed to solve the problem, based on hill climbing (PHC); and iii) a new branch and bound algorithm with the dominance rules and an efficient lower bound was presented to solve the problem optimally, which used the PHC heuristic approach to achieve the upper bound.

This paper considers the single machine scheduling problem with three different due dates in which the actual processing time of the job is a simple deterioration function of the starting time. The goal is to minimize the total costs that contain the earliness, tardiness and due date. We prove that these problems are polynomial time solvable, and we propose the corresponding algorithms to obtain the optimal sequence and due date. [ABSTRACT FROM AUTHOR]

This paper considers the single machine scheduling problem with due window, delivery time and deteriorating job, whose goal is to minimize the window location, window size, earliness and tardiness. Common due window and slack due window are considered. The delivery time depends on the actual processing time of past sequences. The actual processing time of the job is an increasing function of the start time. Based on the small perturbations technique and adjacent exchange technique, we obtain the propositions of the problems. For common and slack due window assignment, we prove that the two objective functions are polynomial time solvable in O (n l o g n) time. We propose the corresponding algorithms to obtain the optimal sequence, window location and window size. [ABSTRACT FROM AUTHOR]

In this paper, parallel machine scheduling problem is considered under due date assignment, earliness, weighted number of tardy jobs, facilities costs and shipping products by limited vehicle capacity. The orders of the customer are presented with a due date. Each order is scheduled and assigned to one of the machines according to due date, delay weight and penalty of increasing of due date and shipped in the batch. The problem is known as NP-hardness, therefore a Genetic Algorithm (GA) is proposed to solve the problem. The results are also compared with the CPLEX solver in the GAMS. Finally, sensitivity analysis for the problem parameters is performed in relation to the objective function. The results showed a direct relationship between objective function with the weighted tardiness and processing time, also an inverse relationship with the number of machines and vehicle capacity. [ABSTRACT FROM AUTHOR]

This paper considers the single machine scheduling problem with due window, delivery time and deteriorating job, whose goal is to minimize the window location, window size, earliness and tardiness. Common due window and slack due window are considered. The delivery time depends on the actual processing time of past sequences. The actual processing time of the job is an increasing function of the start time. Based on the small perturbations technique and adjacent exchange technique, we obtain the propositions of the problems. For common and slack due window assignment, we prove that the two objective functions are polynomial time solvable in O(nlogn) time. We propose the corresponding algorithms to obtain the optimal sequence, window location and window size.

The first objective of this study is to update a capacity constraint to the mixed integer programming model of the unrelated parallel machines scheduling problem. Then, a new proposed algorithm is developed based on the combination between the genetic algorithm with the so-called ISETP heuristics (Initial Sequence based on Earliness-Tardiness criterion on Parallel machine). The new Genetic Algorithm with Initial Sequence based on Earliness-Tardiness criterion on Parallel machine (GAISETP) generates job sequences and allocates them to the machines subject to capacity constraint. A case of automobile component manufacturing company is investigated to test the performance of the proposed method for both small-sized and large-sized problems. The obtained results are very promising both in terms of makespan and earliness-tardiness. [ABSTRACT FROM AUTHOR]

We consider minimizing the maximum earliness in the single-machine scheduling problem with exible maintenance. In this problem, preemptive operations are not allowed, the machine should be shut down to perform maintenance, tool changing or resetting takes a constant time, and the time window inside which maintenance should be performed is predefined. We show that the problem is NP-hard. Afterward, we propose some dominance properties and an efficient heuristic method to solve the problem. Also, we propose a branch-and-bound algorithm, in which our heuristic method, the lower bound, and the dominance properties are incorporated. The algorithm is computationally examined using 3,840 instances up to 14,000 jobs. The results impressively show that the proposed heuristic algorithm obtains the optimal solution in about 99.5% of the cases using an ordinary processor in a matter of seconds at most. [ABSTRACT FROM AUTHOR]

This paper addresses a production scheduling problem in a single-machine environment, where a job can be either early, on time, late, or rejected. In order acceptance and scheduling contexts, it is assumed that the production capacity of a company is overloaded. The problem is therefore to decide which orders to accept and how to sequence their production. In contrast with the existing literature, the considered problem jointly takes into account the following features: earliness and tardiness penalties (which can be linear or quadratic), sequence-dependent setup times and costs, rejection penalties, and the possibility of having idle times. The practical relevance of this new NP-hard problem is discussed and various solution methods are proposed, ranging from a basic greedy algorithm to refined metaheuristics (e.g., tabu search, the adaptive memory algorithm, population-based approaches loosely inspired on ant algorithms). The methods are compared for instances with various structures containing up to 200 jobs. For small linear instances, the metaheuristics are favorably compared with an exact formulation using CPLEX 12.2. Managerial insights and recommendations are finally given. [ABSTRACT FROM AUTHOR]

In this paper, we address the optimal batch sizing and just-in-time scheduling problem where upper and lower bounds on the size of the batches are imposed. The objective is to find a feasible schedule that minimizes the sum of the weighted earliness and tardiness penalties as well as the setup costs, which involves the cost of creating a new batch. We present some structural properties of the optimal schedules and describe solving algorithms for the single machine problem. [ABSTRACT FROM AUTHOR]

Abstract: This paper compares the efficacy of a newly developed network-based mixed-integer programming (MIP) formulation with three existing formulations for the sequence dependent setup scheduling problem with earliness/tardiness penalties. This research shows that the new model is more efficient in terms of computation time for larger multi-machine problems than the existing formulations of these problems. The mixed-integer nature of the formulation allows companies to solve this class of problems with any one of many commonly available integer programming software packages. The presented MIP formulation provides a unique and useful method of conceptualizing and modeling a practical, yet difficult, problem within industry. [Copyright &y& Elsevier]

The single machine scheduling problem with a common due date and non-identical ready times for the jobs is examined in this work. Performance is measured by the minimization of the weighted sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, the application of constructive heuristics that exploit specific characteristics of the problem to improve their performance is investigated. The proposed approaches are examined through a computational comparative study on a set of 280 benchmark test problems with up to 1000 jobs. [ABSTRACT FROM PUBLISHER]

Motivated by just-in-time (JIT) manufacturing, we study the bi-objective scheduling problem of minimizing the total weighted earliness and the number of tardy jobs on a single machine, in which machine idle time and preemption are allowed. The problem is known to be NP-hard. In this paper, we propose a new mathematical model, with nonlinear terms and integer variables which cannot be solved efficiently for medium- and large-sized problems. A method combining the new ranked-based roulette wheel selection algorithm with Pareto-based population ranking algorithm, named nondominated ranking genetic algorithm (NRGA), has been presented to find nondominated solutions in a reasonable time. Various operators and parameters of the proposed algorithm are reviewed to calibrate the algorithm by means of the Taguchi method. A number of numerical examples are solved to demonstrate the effectiveness of the proposed approach. The solutions obtained via NRGA are compared against solutions obtained via ε-constraint method in small-sized problems. Experimental results show that the proposed NRGA is competitive in terms of the quality and diversity of solutions in medium- and large-sized problems. [ABSTRACT FROM AUTHOR]

This study investigates a single-machine scheduling problem with release times. The objective is to minimize the summation of the weighted earliness and tardiness, subject to the number of tardy jobs. The given n jobs with different earliness and tardiness weights have different release times but the same due date. An algorithm is proposed to efficiently generate Pareto-optimal solutions for any possible number of tardy jobs. The accuracy and run time of our algorithm are discussed. In addition, the results show that the proposed algorithm can eliminate most nodes in the branching tree to efficiently find solutions. [ABSTRACT FROM AUTHOR]

This paper considers single machine scheduling problems with linear deteriorating jobs under predictive disruption. In this model, the actual processing time of a job is a increasing linear function of its starting time; and machine is subject to an availability constraint. We assume that an optimal schedule can be obtained by using some algorithms if machine is available at all time. Because of the machine disruption, the original schedule may become infeasible or too far from optimal. We want to create the new schedule that takes into account both the original objective function and a measure of deviation from the original schedule. We consider two versions of the problem. In the first one, the objective is weighted sum of total completion time and total tardiness while in the second one, the objective is weighted sum of total completion time and total earliness. We first prove some properties of the optimal schedule then dynamic programming algorithms are proposed, respectively. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we address a hybrid flow shop scheduling problem considering the minimization of the sum of the total earliness and tardiness penalties. This problem is proven to be NP-hard, and consequently the development of heuristic and meta-heuristic approaches to solve it is well justified. So, we propose an ant colony optimization method to deal with this problem. Our proposed method has several features, including some heuristics that specifically take into account both earliness and tardiness penalties to compute the heuristic information values. The performance of our algorithm is tested by numerical experiments on a large number of randomly generated problems. A comparison with solutions performance obtained by some constructive heuristics is presented. The results show that the proposed approach performs well for this problem. [Copyright &y& Elsevier]

The objective of this paper is to determine a schedule for parallel flow line with bicriteria objective of minimizing the total tardiness and earliness of jobs. An enhancement to its basic greedy randomized adaptive search procedure (GRASP) is used in conjunction with genetic algorithm (GA) and particle swarm optimization (PSO). The feasible solution of GRASP construction phase is used as initial population for both GA and PSO. A number of problems are solved, by varying the number of jobs, lines, and machines, using the hybrid PSO, hybrid GA, PSO, and GA-based methods and the results are compared. [ABSTRACT FROM AUTHOR]

The article presents a study on a new, efficient and nontrivial Mixed Integer Program (MIP) formulation that can be used on variety of single machine scheduling problem. It notes that the introduced MIP is closely related to the well-known time-indexed MIP formulation but utilizes less variables and constraints. Based on the experiments on academic benchmarks and real-life industrial problems, it is concluded that the generic MIP formulation is efficient.

This paper investigates a novel multi-objective model for a permutation flow shop scheduling problem that minimizes both the weighted mean earliness and the weighted mean tardiness. Since a flow shop scheduling problem has been proved to be NP-hard in a strong sense, a new hybrid multi-objective algorithm based on shuffled frog-leaping algorithm (SFLA) and variable neighborhood search (VNS) is devised to find Pareto optimal solutions for the given problem. To validate the performance of the proposed hybrid multi-objective shuffled frog-leaping algorithm (HMOSFLA) in terms of solution quality and diversity level, various test problems are examined. Further, the efficiency of the proposed algorithm, based on various salient metrics, is compared against two well-known multi-objective genetic algorithms: NSGA-II and SPEA-II. Our computational results suggest that the proposed HMOSFLA outperforms the two foregoing algorithms, especially for large-sized problems. [ABSTRACT FROM AUTHOR]

In this paper, a single-machine scheduling model with a given common due date and simple linear processing times was considered. The objective is the total weighted tardiness penalty and earliness award. Some polynomial time solvable cases for this problem are given. A dynamic programming algorithm was provided and a branch and bound algorithm for general case of the problem was provided based on a rapid method for estimating the lower bound. [ABSTRACT FROM AUTHOR]

In this paper, a single-machine scheduling model with a given common due date is considered. Job processing time is a linear decreasing function of its starting time. The objective function is to minimize the total weighted earliness award and tardiness penalty. Our aim is to find an optimal schedule so as to minimize the objective function. As the problem is NP-hard, some properties and polynomial time solvable cases of this problem are given. A dynamic programming algorithm for the general case of the problem is provided. [ABSTRACT FROM AUTHOR]

The common due window scheduling problem with batching on a single machine is dealt with to minimize the total penalty of weighted earliness and tardiness. In this paper it is assumed that a job incurs no penalty as long as it is completed within the common due window. It is the first time for the due window scheduling to be extended to this situation so that jobs can be processed in batches. An unbounded version of batch scheduling is also considered. Hence, jobs, no matter how many there are, can be processed in a batch once the machine is free. For two cases that the location of due window is either a decision variable or a given parameter, polynomial algorithms are proposed based on several optimal properties. [ABSTRACT FROM AUTHOR]

In this note, we study a single-machine scheduling problem with deteriorating jobs whose processing times are an increasing function of their start times. The objective is to determine the optimal due-date and schedule simultaneously to minimize the total of due-date, earliness and tardiness penalties. We give a concise analysis of the problem and provide a polynomial time algorithm to solve the problem. Moreover, the algorithm can be easily applied to the 'mirror' scheduling problem in which the actual processing time of a job is a decreasing function of its starting time. [ABSTRACT FROM AUTHOR]

The aim of this article is to point out some flaws in the mathematical programming model proposed by Tamer Eren [Human and Machine Effects in a Just-In-Time Scheduling Problem, Human Factors and Ergonomics in Manufacturing, 19(4), 294-299 (2009)]. Ignoring these flaws may cause unexpected computational results. © 2010 Wiley Periodicals, Inc. [ABSTRACT FROM AUTHOR]