Search

We propose a dynamic ensemble selection method, META-DES-AAP, to predict the success of bank telemarketing sales of time deposits. Unlike existing machine learning-based marketing sales prediction methods focusing only on prediction accuracy, META-DES-AAP considers the accuracy and average profit maximization. In META-DES-AAP, to consider both accuracy and average profit in the framework of dynamic ensemble selection using meta-training, a multi-objective optimization algorithm is designed to maximize the accuracy and average profit for base classifiers selection. Base classifiers suitable for each test telemarketing campaign are integrated according to the dynamic-based base classifiers integration method. Experimental results on bank telemarketing data show that META-DES-AAP achieves the best accuracy and the largest average profit when compared across several state-of-the-art machine learning methods. In addition, the factors influencing telemarketing on the average predicted probability of telemarketing success and average profit obtained by META-DES-AAP are analyzed.

Classification is a vital task in machine learning. By learning patterns of samples of known categories, the model can develop the ability to distinguish the categories of samples of unknown categories. Noticing the advantages of the clustering method in cluster structure analysis, we combine the clustering and classification methods to develop the novel cluster-based intelligence ensemble learning (CIEL) method. We use the clustering method to analyze the inherent distribution of the data and divide all the samples into clusters according to the characteristics of the dataset. Then, for each specific cluster, we use different classification algorithms to establish the corresponding classification model. Finally, we integrate the prediction results of each base classifier to form the final prediction result. In view of the problem of parameter sensitivity, we use a swarm intelligence algorithm to optimize the key parameters involved in the clustering, classification, and ensemble stages in order to boost the classification performance. To assess the effectiveness of CIEL, we perform tenfold cross-validation experiments on the 24 benchmark datasets provided by UCI and KEEL. Designed to improve the performance of the classifiers, CIEL outperforms other popular machine learning methods such as naive Bayes, k-nearest neighbors, random forest, and support vector machine.

Credit risk assessment is a crucial task in the peer-to-peer (P2P) lending industry. In recent years, ensemble learning methods have been verified to perform better in default prediction than individual classifiers and statistical techniques. Real-world loan datasets are imbalanced; however, most studies focus on enhancing overall prediction accuracy rather than improving the identification ability of real default loans. Moreover, some of the features that are significantly correlated with default rates are not attached importance in the model construction of previous studies. To fill these gaps, we propose a distance-to-model and adaptive clustering-based multi-view ensemble (DM–ACME) learning method for predicting default risk in P2P lending. In this method, multi-view learning and an adaptive clustering method are explored to produce an ensemble of diverse ensembles constituted by gradient boosting decision trees. A novel combination strategy called distance-to-model and a soft probability fashion are embedded for model integration. To verify the effectiveness of the proposed ensemble approach, comprehensive analysis on DM–ACME, comparative experiments with several state-of-the-art methods, and feature importance evaluation are conducted with the data provided by Lending Club. Experimental results demonstrate the superiority of the proposed method as well as indicate the importance of some features in loan default prediction.

This study considers an integrated production, inventory, and outbound distribution scheduling model that arises in a three-stage supply chain consisting of three parts: a supplier, a manufacturer, and several customers. The manufacturer receives a set of two-stage orders to process a specific set of jobs (products) for the customers. These jobs are first partly processed by the supplier, and delivered to the manufacturer by vehicles immediately at additional delivery costs depending on the delivered jobs. The partly processed jobs are then processed by the manufacturer, and delivered to their respective customers by transporters with fixed delivery departure times. A finished job is either kept in a temporary warehouse before it is delivered at an inventory cost, or delivered to its customer immediately. Each job is associated with a desired due date, and late deliveries are not accepted. The objective is to determine schedules for processing the jobs, and identify delivery schedules from the manufacturer to all customers such that the weighted sum of the weighted number of late jobs, inventory cost, and delivery cost is minimized. For each considered problem, we investigate its computational complexity, and develop pseudo-polynomial or polynomial-time solution algorithm, if viable. Using randomly generated data, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms.

We study the integrated production and multiple trips vehicle routing problem with time windows and uncertain travel times involving two phases. The first phase considers scheduling a set of jobs on parallel machines with machine-dependent ready times, and the second phase focuses on the delivery of completed jobs by a fleet of identical vehicles, which may differ in their ready times. In addition, the travel times in distribution are uncertain. The objective is to minimize the total cost comprising the travel cost and penalty cost caused by tardiness. We present a robustness approach, known as “Elastic p-Robustness”, to deal with travel time variations when historical risk data are limited or non-existent, and develop a memetic algorithm with an effective search strategy to solve the problem. We conduct numerical studies on randomly generated data based on real experience to assess the effectiveness and efficiency of the proposed method. The computational results show that the proposed solution approach yields relatively good solutions in comparison with current mainstream heuristic algorithms.

This paper investigates a home delivery and installation routing problem with synchronization constraints stemming from a home industry company in China who provides the last-mile delivery of home decoration and furniture. The company first arranges for products to be delivered from door to door, and later the technicians come to perform the installation service for the customers. The products for each customer must be firstly delivered to the customer by a vehicle and then installed by technicians. The objective is to identify the optimal delivery routes of the vehicles and optimal service routes of the technicians so as to minimize the total travel distance of the delivery and service routes. A deep reinforcement learning method in an Encoder-Decoder fashion with multi-head attention mechanism and beam search strategy is developed to solve the problem. To evaluate the designed method, extensive numerical experiments based on real service networks provided by the company are conducted. The results show that the proposed method can effectively solve the problem, which outperforms some classical strategies, and some meaningful management implications are provided.

This paper studies the resilience of logistics network against node failures in the context of express industry owing to disruption in the network. By considering the flow capacity between the nodes and the impact of each node's failure, we propose a load redistribution mechanism in the presence of cascading failures which is akin to a criticality-based resilience assessment or stress testing the supply chain. To further investigate the impact of the node/nodes failure, we simulate and propose algorithms for two cascading failure scenarios, illustrating the different adjustment schemes for resilience improving strategies. A sensitivity analysis with managerial insights is also performed to investigate the effect of the adjustment schemes on the criticality of the nodes and the resilience of the express logistics network.

We study the scheduling problem where a set of jobs has already been scheduled for processing on identical parallel machines to minimize the total completion time under the assumption that all the jobs are available at time zero. However, before processing begins, some jobs are delayed and become unavailable at time zero, so all the jobs need to be rescheduled with a view to not causing excessive schedule disruption with respect to the original schedule. To reduce the negative impact of job unavailability and achieve an acceptable service level, one option in rescheduling the jobs is to reject a subset of the jobs at a cost (the rejection cost). Three criteria are involved: the total completion time of the accepted jobs in the adjusted schedule, the degree of disruption measured by the maximum completion time disruption to any accepted job between the original and adjusted schedules, and the total rejection cost. The overall objective is to minimize the former criterion, while keeping the objective values of the latter two criteria to no greater than the given limits. We present two exact methods to solve the problem: (i) A dynamic programming based approach, establishing that the problem is NP-hard in the ordinary sense when the number of machines is fixed. (ii) An enhanced branch-and-price method that includes several features such as execution of the differential evolution algorithm for finding good initial feasible solutions and solving the pricing sub-problem, inclusion of reduced cost fixing during the inner iterations of the algorithm, and use of a heuristic procedure for constructing a good integer feasible solution. We perform extensive computational experiments to assess the efficiency of the proposed algorithms. The computational results demonstrate that the incorporated enhancements greatly improve the performance of the algorithm.

Colorectal cancer (CRC) is the third leading cause of cancer deaths in the world, which mostly stems from precancerous polyps. Early detection and accurate classification of polyps play a vital role in colonoscopy. It makes sense to automatically detect the polyp and give a real-time classification feedback according to popular Yamada classification guidance during colonoscopy progress. We propose an interpretable deep neural network method, called multi-task real-time deep neural network with Shapley additive explanations, for polyp detection, polyp classification and polyp segmentation under colonoscopy. To the best of our knowledge, this is the first time to perform polyp classification according to Yamada classification guidance under colonoscopy with a deep learning method. To validate the performance of our proposed method, we conduct various comparative experiments on popular CVC-CLINIC and CVC-COLON datasets. We adopt various performance indicators, including area under receiver operating characteristics curve (AUC), precision, recall, F1 score, accuracy, and mean intersection over union (mIoU). The proposed method achieves satisfactory real-time performance in terms of polyp detection module, polyp classification module and polyp segmentation module. The experimental results show the overwhelming performance of our proposed method compared with other deep learning methods. We have achieved satisfying operating efficiency and interpretable feedback to meet the requirements of the colorectal surgeon, which provides an valuable decision support and reduces the rate of missed diagnosis and misdiagnosis of polyps in the process of colonoscopy.

This paper investigates the retailer's trade credit strategy and ordering policy in a two-echelon supply chain consisting of one supplier and one retailer. The retailer accepts upstream trade credit from the supplier while offers downstream trade credit to consumers, and the relationship between the upstream and downstream credit period is uncertain. The market demand depends on both the downstream trade credit and the random initial demand rate, and granting downstream trade credit increases not only sales but also default risk. This paper tries to find the retailer's optimal decisions on credit period, replenishment cycle, and order quantity so as to maximize the retailer's profit. It is shown that there exists a unique decision for the retailer. Some numerical examples are given to verify our results and provide more managerial insights. It is found that the retailer is more willing to provide trade credit under higher marginal profit, and that providing downstream trade credit is beneficial to both the retailer and supplier.

The occurrence of disasters often causes a large number of wounded persons. The rapid rescue and transport of wounded persons for medical care is a key concern of emergency management. To maximize the number of survivors, we propose a new transport strategy based on injury classification, called the Red-Yellow-Green-Sequential (RYGS) transport strategy, which prioritizes the transport order by the degree of injury of the wounded persons. To solve this intractable problem, we propose an improved ant colony optimization algorithm (IACO) to solve it approximately. IACO not only involves a pheromone updating method according to the characteristics of the problem itself, but also combines the particle swarm optimization algorithm and the genetic algorithm to avoid local convergence. Through numerical studies, we demonstrate that IACO outperforms ACO under different transport strategies in different scales and scenarios. In addition, we demonstrate through numerical studies the superiority of RYGS among three transport strategies in different scenarios and scales. We also demonstrate that the combination of IACO and RYGS performs best in different scenarios and scales. Finally, we conduct a sensitivity analysis to analyze the impacts of the different medical resources on the objective for the problems with different combinations of scales and scenarios based on IACO. We also discuss the practical implications of the findings for emergency management.

Pan-sharpening applies details injection to fuse a multispectral (MS) image with its corresponding panchromatic (PAN) image to produce a synthetic image. Theoretically, the synthetic image's spectral resolution should equal that of the MS image and its spatial resolution is the same as that of the PAN image. However, for existing pan-sharpening methods, the trade-off between the spectral and intensity information in the process of details injection is insufficient, resulting in spatial or spectral distortion of the fused image. In this paper we propose a novel pan-sharpening algorithm based on multi-objective decision for multi-band remote sensing images to improve the quality of the fused image. The proposed method focuses on developing a parametric model from a multi-objective perspective to simultaneously maximize the quality of all the pixels in the fused image. We introduce a details injection approach to enhance the edge and texture of the MS image. We design an efficient spectral fidelity fusion model based on the injected details using spectral modulation to pan-sharpen the MS image. We provide an algorithm based on multi-objective decision to solve this model. The main advantage of the proposed method is that it can provide effective spectral modulation to eliminate the adverse effects of details injection. We conduct experiments on simulated and real satellite image datasets to evaluate the proposed method. The results show that our method achieves superior performance to other state-of-the-art methods.

We consider the problem of scheduling n nonresumable and simultaneously available jobs on a single machine with several agents. Each job belongs to one of the agents, each of which competes for the use of the machine to process its own jobs to meet its own scheduling criterion. The machine has a fixed interval during which it is unavailable to process the jobs. The due dates of the last agent’s jobs are decision variables, which are determined by the unrestricted (different) due date assignment model, while the due dates of each of the other agents’ jobs are given in advance. The last agent wishes to minimize the sum of the due date assignment cost and weighted number of its tardy jobs, while each of the other agents seeks to minimize the maximum value of a regular scheduling function of its jobs, the total completion time of its jobs, or the weighted number of its tardy jobs. The overall objective is to minimize the last agent’s criterion, while keeping each of the other agents’ criterion values no greater than a given limit. We analyze the computational complexity, and devise pseudo-polynomial dynamic programming (DP) solution algorithms and mixed integer linear programming (MILP) formulations for the considered problems. Finally, we compare the performance of the DP solution algorithms against the corresponding MILP formulations with randomly generated instances.

We consider parallel-machine scheduling of deteriorating jobs in a disruptive environment in which some of the machines will become unavailable due to potential disruptions. This means that a disruption to some of the machines may occur at a particular time, which will last for a period of time with a certain probability. If a job is disrupted during processing by a disrupted machine and it does not need (needs) to re-start after the machine becomes available again, it is called the resumable (non-resumable) case. By deteriorating jobs, we mean that the actual processing time of a job grows when it is scheduled for processing later because the machine efficiency deteriorates over time due to machine usage and aging. However, a repaired machine will return to its original state of efficiency. We consider two cases, namely performing maintenance immediately on the disrupted machine when a disruption occurs and not performing machine maintenance. In each case, the objective is to determine the optimal schedule to minimize the expected total completion time of the jobs in both non-resumable and resumable cases. We determine the computational complexity status of various cases of the problem, and provide pseudo-polynomial-time solution algorithms and fully polynomial-time approximation schemes for them, if viable.

We study a two-agent multi-facility order scheduling with ready times.We derive several dominance properties and a lower bound on the optimal solution.We present algorithms based on particle swarm optimization (PSO) and opposite-based particle swarm optimization (O-PSO) to obtain near-optimal solutions. Recently, multi-agent scheduling and customer order scheduling have separately received much attention in scheduling research. However, the two-agent concept has not been introduced into order scheduling in the multi-facility setting. To fill this research gap, we consider in this paper two-agent multi-facility order scheduling with ready times. The objective is to minimize the total completion time of the orders of one agent, with the restriction that the total completion time of the orders of the other agent cannot exceed a given limit. We first develop a branch-and-bound algorithm incorporating several dominance rules and a lower bound to solve this intractable problem. We then propose a particle swarm optimization algorithm (PSO), an opposite-based particle swarm optimization (OPSO) algorithm, and a particle swarm optimization algorithm with a linearly decreasing inertia weight (WPSO) to obtain near-optimal solutions. Applying two levels of number of particles and number of neighbourhood improvements for the PSO and OPSO algorithms, we execute them at a fixed inertia weight, and execute WPSO at a varying decreasing inertia weight. We perform a one-way analysis of variance of the performance of the five PSO algorithms in tackling the problem with small and big orders. We demonstrate through extensive computational studies that the proposed PSO algorithms are very efficient in quickly finding solutions that are very close to the optimal solutions.

Display Omitted The multiple objectives and the sequence-dependent setup times are considered in the permutation flowshop scheduling problem.The extension of conventional single-objective iterated local search (ILS) to solve multi-objective combinatorial optimization problem.A Pareto based variable depth search is designed to act as the multi-objective local search phase in the multi-objective ILS.The experimental results on some benchmark problems show that the proposed multi-objective ILS outperforms several powerful multi-objective evolutionary algorithms in the literature.A multi-objective iterated local search is proposed. Due to its simplicity yet powerful search ability, iterated local search (ILS) has been widely used to tackle a variety of single-objective combinatorial optimization problems. However, applying ILS to solve multi-objective combinatorial optimization problems is scanty. In this paper we design a multi-objective ILS (MOILS) to solve the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times to minimize the makespan and total weighted tardiness of all jobs. In the MOILS, we design a Pareto-based variable depth search in the multi-objective local search phase. The search depth is dynamically adjusted during the search process of the MOILS to strike a balance between exploration and exploitation. We incorporate an external archive into the MOILS to store the non-dominated solutions and provide initial search points for the MOILS to escape from local optima traps. We compare the MOILS with several multi-objective evolutionary algorithms (MOEAs) shown to be effective for treating the multi-objective permutation flowshop scheduling problem in the literature. The computational results show that the proposed MOILS outperforms the MOEAs.

The estimation of the loss and prediction of the casualties in earthquake-stricken areas are vital for making rapid and accurate decisions during rescue efforts. The number of casualties is determined by various factors, necessitating a comprehensive system for earthquake-casualty prediction. To obtain accurate prediction results, an effective prediction method based on stacking ensemble learning and improved swarm intelligence algorithm is proposed in this study, which comprises three parts: (1) applying multiple base learners for training, (2) using a stacking strategy to integrate the results generated by multiple base learners to obtain the final prediction results, and (3) developing an improved swarm intelligence algorithm to optimize the key parameters in the prediction model. To verify the effectiveness of the model, we collected data pertaining to earthquake destruction from 1966 to 2017 in China. Experiments were conducted to compare the proposed method with popular machine learning methods. It was found that the stacking ensemble learning method can effectively integrate the prediction results of the base learner to improve the performance of the model, and the improved swarm intelligence algorithm can further improve the prediction accuracy. Moreover, the importance of each feature was evaluated, which has important implications for future work such as casualty prevention and rescue during earthquakes.

The order scheduling problem is receiving increasing attention in the relatively new but creative area of scheduling research. In order scheduling, several orders are processed on multiple machines, and each order comprises multiple components. The order completion time is defined as the time at which all components in an order are completed. In previous studies, the processing times of all components were fixed in order scheduling problems. This is unreasonable because a steady decline in processing time usually occurs when the same task is performed repeatedly in practical situations. Therefore, we propose a multiple-machine order scheduling problem with a learning effect to minimize the total tardiness. We develop a branch-and-bound algorithm incorporating certain dominance rules and three lower bounds for obtaining the optimal solution. Subsequently, we propose simulated annealing, particle swarm optimization, and order-scheduling MDD algorithms for obtaining a near-optimal solution. In addition, the experimental results of all proposed algorithms are provided. We propose a multiple-machine order scheduling problem with a learning effect to minimize the total tardiness.We derive several dominance rules and three lower bounds applied in a branch-and-bound algorithm for an optimal solution.We propose simulated annealing and particle swarm optimization algorithms for obtaining a near-optimal solution.

This paper considers two-agent just-in-time scheduling where agents A and B have to share m unrelated parallel machines for processing their jobs. The objective of agent A is to maximize the weighted number of its just-in-time jobs that are completed exactly on their due dates, while the objective of agent B is either to maximize its maximum gain (income) from its just-in-time jobs or to maximize the weighted number of its just-in-time jobs. We provide a bicriterion analysis of the problem, which seek to find the Pareto-optimal solutions for each combination of the two agents׳ criteria. When the number of machines is part of the problem instance, both the addressed problems are NP-hard in the strong sense. When the number of machines is fixed, we show that the problem of maximizing agent A׳s weighted number of just-in-time jobs while maximizing agent B׳s maximum gain can be solved in polynomial time, whereas the problem of maximizing both agents׳ weighted numbers of just-in-time jobs is NP-hard. For the latter problem, we also provide a pseudo-polynomial-time solution algorithm, establishing that it is NP-hard in the ordinary sense, and show that it admits a fully polynomial-time approximation scheme (FPTAS) for finding an approximate Pareto solution.

We consider a scheduling problem where a set of jobs has already been assigned to identical parallel machines that are subject to disruptions with the objective of minimizing the total completion time. When machine disruptions occur, the affected jobs need to be rescheduled with a view to not causing excessive schedule disruption with respect to the original schedule. Schedule disruption is measured by the maximum time deviation or the total virtual tardiness, given that the completion time of any job in the original schedule can be regarded as an implied due date for the job concerned. We focus on the trade-off between the total completion time of the adjusted schedule and schedule disruption by finding the set of Pareto-optimal solutions. We show that both variants of the problem are NP -hard in the strong sense when the number of machines is considered to be part of the input, and NP -hard when the number of machines is fixed. In addition, we develop pseudo-polynomial-time solution algorithms for the two variants of the problem with a fixed number of machines, establishing that they are NP -hard in the ordinary sense. For the variant where schedule disruption is modeled as the total virtual tardiness, we also show that the case where machine disruptions occur only on one of the machines admits a two-dimensional fully polynomial-time approximation scheme. We conduct extensive numerical studies to evaluate the performance of the proposed algorithms.

Integrated production and batch delivery scheduling with two agents is considered.Constrained optimization problems on various criteria of the two agents are addressed.Computational complexity status and solution procedures are developed for the problems.Numerical studies are conducted to evaluate the performance of the algorithms. We consider integrated production and batch delivery scheduling in a make-to-order production system involving two competing agents, each of which having its own job set competes to process its jobs on a shared single machine. To save the delivery cost, the jobs of the same agent can be processed and delivered together batches. The completion time of each job in the same batch coincides with the batch completion time. A batch setup time is incurred before the processing of the first job in each batch. Each of the agents wants to minimize an objective function depending on the completion times of its own jobs. The goal is to determine a schedule for all the jobs of the two agents that minimizes the objective function of one agent, while keeping the objective function value of the other agent below or at a given value. For each of the problems under consideration, we either provide a polynomial-time algorithm to solve it or show that it is NP -hard. In addition, for each of the NP -hard problems, we present a mixed integer linear programming (MILP) formulation and provide a pseudo-polynomial dynamic programming algorithm, establishing that it is NP -hard in the ordinary sense only, and show that it admits an efficient fully polynomial-time approximation scheme, if viable. Finally, we compare the performance of the pseudo-polynomial dynamic programming algorithms against the corresponding MILP formulations with randomly generated instances.

This paper addresses some scheduling problems with two competing agents, called agents A and B, respectively, each of which has a set of independent nonpreemptive jobs to be scheduled for processing on a common machine. The due dates of jobs in each job set are considered as given parameters and must be assigned to individual jobs. Each agent wants to minimize a certain objective function that depends on the completion times and due dates of its jobs only. The goal is to find a feasible schedule and determine the due dates for all jobs of the two agents that minimizes the objective of agent A while keeping the objective of agent B below or at a fixed level Q. We consider nine problems arising from different criteria combinations for the two agents, depending on the criterion of each agent including the maximum lateness, total (weighted) tardiness, (weighted) number of tardy jobs, and total weighted tardiness and earliness, and state the complexity results for most of problems under consideration.

In this paper we consider two agents that compete on the use of a common processor. Each of the agents has a set of jobs that have to be processed on the same machine without preemption. Each of the agents wants to minimize an objective function that depends on the completion time of its own jobs. In addition, each job has different release dates. In the presence of unequal release dates, it is sometimes advantageous to form a non-full batch, while in other situations it is a better strategy to wait for future job arrivals in order to increase the fullness of the batch. The objective is to find a schedule that performs well with respect to the objectives of both agents. To solve this difficulty problem, we construct a branch-and-bound solution scheme incorporating these bounds and some dominance rules for the optimal solution. In view of the advantage of combining local and global searches in the honey-bees optimization algorithm, we attempt to use a marriage in honey-bees optimization algorithm (MBO) to find near-optimal solutions. We conduct extensive computational experiments to evaluate the performance of the algorithms.

We study some two-agent single-machine scheduling problems with increasing linear job deterioration.We consider six different combinations of two-agent objective functions.We discuss complexities and develop polynomial-time algorithms of the proposed problems. We consider several two-agent single-machine scheduling problems with deteriorating jobs. By deteriorating jobs we mean that the actual processing time of any job of the two agents is an increasing linear function of its starting time. Each agent wants to minimize a certain objective function, which depends on the completion times of its jobs only. The goal is to schedule the jobs such that the performance of the schedule is satisfactory with respect to the objective functions of both agents. We consider six scheduling problems associated with different combinations of the two agents' objective functions, which include the maximum cost, total weighted completion time, discounted total weighted completion time, maximum earliness cost, total earliness, and total weighted earliness. We examine different scenarios depending on the trade-off between the two agents. Under each scenario, we address the computational complexity and solvability issues of various problems that seek to find the optimal solution for one agent, subject to an upper bound on the maximum (earliness) cost of the other agent.

We address two scheduling problems arising when two agents (agents A and B ), each with a set of jobs, compete to perform their respective jobs on a common machine, where the due dates of agent A ’s jobs are decision variables to be determined by the scheduler. Specifically, the objective is to determine the optimal due dates for agent A ’s jobs and the job sequence for both agents’ jobs simultaneously to minimize the total cost associated with the due date assignment and weighted number of tardy jobs of agent A , while keeping the maximum of regular functions (associated with each B -job) or the number of tardy jobs of agent B below or at a fixed threshold. We prove that both problems are NP -hard in the strong sense and develop polynomial or pseudo-polynomial solutions for some important special cases.

In this paper, we explore a single-machine scheduling problem in which the processing time of a job is a linear increasing function of its starting time. The objective is to determine the optimal due date and schedule simultaneously to minimize a cost function that includes the weighted number of tardy jobs and the due date assignment cost. We show that the problem is NP-hard in the ordinary sense. In addition, we propose two dynamic programming algorithms and a fully polynomial-time approximation scheme for the problem.

We study a re-entrant permutation flowshop scheduling problem to minimize the makespan.We develop a memetic algorithm (MA) to obtain near-optimal solutions for the problem.Compared with two existing heuristics and CPLEX, MA is effective and outperforms the two existing heuristics and CPLEX. 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.

This paper addresses the problem of scheduling n nonresumable and simultaneously available jobs on a single machine, where the machine has a fixed unavailability interval, and the jobs are delivered in batches to the customers. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The goal is to find the optimal delivery date for each job and an optimal job sequence to minimize the sum of total flow time and batch delivery cost. The problem is shown to be NP-hard based on a reduction from the Equal-Size Partition Problem. Then a pseudo-polynomial time algorithm is developed, establishing that it is NP-hard in the ordinary sense. Finally, by applying the interval partitioning technique and the rounding technique, a fully polynomial time approximation scheme (FPTAS) and a bicriteria fully polynomial time approximation scheme are developed, which run in time On5e2+n5logn and On6e, respectively.

Recently, machine scheduling problems with deteriorating jobs have received interestingly attention from the scheduling research community. Majority of the research assumed that the actual job processing time is an increasing function of its starting time. However, no job can remain undeteriorated indefinitely in real life situations. This paper considers a single-machine scheduling problem with a truncated linear deteriorating effect and ready times. By the truncated linear deteriorating effect, it means that the actual processing time of a job is a function of its starting time and a control parameter. The objective is to minimize the makespan. A mixed integer programming model and a branch-and-bound algorithm coupled with several dominance properties and two lower bounds are developed to search for the optimal solution. In addition, an ant colony and a Tabu search algorithm where each is refined by the three improvements are also proposed for a near-optimal solution, respectively. A computational experiment is then conducted to evaluate the impacts of the used parameters on the performances of the proposed algorithms.

This study considers an NP-hard problem of minimizing the total tardiness on a single machine with arbitrary release dates and position-dependent learning effects. A mixed-integer programming (MIP ) model is first formulated to find the optimal solution for small-size problem instances. Some new dominance rules are then presented which provide a sufficient condition for finding local optimality. The branch-and-bound (B& B) strategy incorporating with several dominance properties and a lower bound is proposed to derive the optimal solution for medium- to-large-size problem instances, and four marriage-in-honey-bees optimization algorithms (MBO) are developed to derive near-optimal solutions for the problem. To show the effectiveness of the proposed algorithms, 3600 situations with 20 and 25 jobs, are randomly generated for experiments.

This paper considers single-machine scheduling problems with simultaneous consideration of due date assignment, past-sequence-dependent (p-s-d) delivery times, and position-dependent learning effects. By p-s-d delivery times, we mean that the delivery time of a job is proportional to the job’s waiting time. Specifically, we study four variants of the problem: (i) the variant of total earliness and tardiness with common due date assignment (referred to as TETDC), (ii) the variant of total earliness and weighted number of tardy jobs with CON due date assignment (referred to as TEWNTDC), (iii) the variant of total earliness and weighted number of tardy jobs with slack due date assignment (referred to as TEWNTDS), and (iv) the variant of weighted number of tardy jobs with different due date assignment (referred to as WNTDD). We derive the structural properties of the optimal schedules and show that the variants TETDC, TEWNTDC and TEWNTDS are all polynomially solvable. Although the complexity status of the variant WNTDD is still open, we show that two special cases of it are polynomially solvable.

We consider single-machine batch delivery scheduling with an assignable common due date and controllable processing times, which vary as a convex function of the amounts of a continuously divisible common resource allocated to individual jobs. Finished jobs are delivered in batches and there is no capacity limit on each delivery batch. We first provide an O(n^5) dynamic programming algorithm to find the optimal job sequence, the partition of the job sequence into batches, the assigned common due date, and the resource allocation that minimize a cost function based on earliness, tardiness, job holding, due date assignment, batch delivery, and resource consumption. We show that a special case of the problem can be solved by a lower-order polynomial algorithm. We then study the problem of finding the optimal solution to minimize the total cost of earliness, tardiness, job holding, and due date assignment, subject to limited resource availability, and develop an O(nlogn) algorithm to solve it.

In recent 10 years, the multi-agent idea applied in scheduling issues has received continuing attention. However, the study of the multi-agent scheduling with deteriorating jobs is relatively limited. In light of this, this paper deliberates upon a two-agent single-machine scheduling problem with deteriorating jobs. Taking the proposed model, the actual processing time of a job from both the first agent and the second agent is modeled as a linearly increasing function of its starting time. The goal of this paper is to minimize the total weighted number of tardy jobs of the first agent subject to the condition that the maximum lateness of the second agent is allowed to have an upper bound. The complexity of the model concerned in the paper is claimed as an NP-hard one. Following that, several dominance rules and a lower bound are proposed to be applied in a branch-and-bound algorithm for the optimal solution, and a tabu algorithm is applied to find near-optimal solutions for the problem. The simulation results obtained from all the proposed algorithms are also reported.

This paper addresses a batch delivery single-machine scheduling problem in which jobs have an assignable common due window. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find the optimal size and location of the window, the optimal dispatch date for each job, as well as an optimal job sequence to minimize a cost function based on earliness, tardiness, holding time, window location, window size, and batch delivery. We show that the problem can be optimally solved in O ( n 8 ) time by a dynamic programming algorithm under a reasonable assumption on the relationships among the cost parameters. A computational experiment is also conducted to evaluate the performance of the proposed algorithm. We also show that some special cases of the problem can be optimally solved by lower order algorithms.

This paper considers a variation of the classical single machine scheduling problem with tool changes. In the variation, two sets of jobs, namely special jobs and normal jobs, are considered. By special jobs, we mean that each special job must be processed within the first prefixed time units of a tool life. To solve the scheduling problem with small size and moderate size, we propose two mathematical programming models. To solve the scheduling problem with large size, we propose three sets of algorithms and focus on the performance of six algorithms based on the studies of a new bin packing problem. Worst-case analysis is conducted. Numerical experiment shows that each of the six algorithms can solve instances with up to 5000 jobs in about 0.5 s with an average relative error less than 4%.

This paper attempts to study on the single machine scheduling problems with two synergetic agents, each has a set of nonpreemptive jobs and a regular objective function depending on the completion times of its jobs only. It is not only necessary to satisfy the constraints of each agents objective function, it is necessary to minimize an aggregate increasing objective function of two agents’ objective function. Furthermore, this paper proposes a new kind of machine maintenance: piece-rate maintenance, which depicts the scenario that machine maintenance is implemented once every a fixed number of jobs is completed. Hence, it explores into the single machine scheduling problems with two synergetic agents and piece-rate maintenance. If the regular objective function of each job is polynomial, it can be observed that these problems are all polynomially solvable.

In many management situations, multiple agents compete on the usage of common processing resources. On the other hand, the importance of the ready times can be shown in Wafer fabrication with the presence of unequal ready times. It is sometimes advantageous to form a non-full batch, while in other situations it is a better strategy to wait for future job arrivals in order to increase the fullness of the batch. However, research on scheduling with two-agent and ready time simultaneously is relatively unexplored. This paper addresses a single-machine two-agent scheduling problem with ready times. The aim is to find an optimal schedule to minimize the total completion time of the jobs of the first agent with the restriction that total completion time is allowed an upper bound for the second agent. To the best of our knowledge, the problem under study has not been considered. Firstly, we show that the proposed problem is strongly NP-hard. Following that, we then develop a branch-and-bound, an ant colony, and four genetic algorithms for an optimal and near-optimal solution, respectively. In addition, the extensive computational experiments are also given.

This paper addresses a two-agent scheduling problem on a single machine where the objective is to minimize the total weighted earliness cost of all jobs, while keeping the earliness cost of one agent below or at a fixed level Q. A mixed-integer programming (MIP) model is first formulated to find the optimal solution which is useful for small-size problem instances. To solve medium- to large-size problem instances, a branch-and-bound algorithm incorporating with several dominance properties and a lower bound is then provided to derive the optimal solution. A simulated annealing heuristic algorithm incorporating with a heuristic procedure is developed to derive the near-optimal solutions for the problem. A computational experiment is also conducted to evaluate the performance of the proposed algorithms.

This paper addresses a two-agent scheduling problem on a single machine with arbitrary release dates, where the objective is to minimize the tardiness of one agent, while keeping the lateness of the other agent below or at a fixed level Q. A mixed integer programming model is first presented for its optimal solution, admittedly not to be practical or useful in the most cases, but theoretically interesting since it models the problem. Thus, as an alternative, a branch-and-bound algorithm incorporating with several dominance properties and a lower bound is provided to derive the optimal solution and a marriage in honey-bees optimization algorithm (MBO) is developed to derive the near-optimal solutions for the problem. Computational results are also presented to evaluate the performance of the proposed algorithms.

Maji et al. introduced the concept of intuitionistic fuzzy soft sets which is a generalization of fuzzy soft sets and standard soft sets. In this paper, we further discuss the operation properties and algebraic structure of intuitionistic fuzzy soft sets. The lattice structures of intuitionistic fuzzy soft sets are derived. The notions of (γ,δ)-intuitionistic fuzzy soft equalities are introduced and their basic properties are investigated. The relationships between (γ,δ)-intuitionistic fuzzy soft equalities and soft equalities introduced by Qin and Hong are developed. The notion of a mapping on intuitionistic fuzzy soft classes is introduced and several properties of the image and inverse image of intuitionistic fuzzy soft sets are presented.