Simultaneous dock assignment and sequencing of inbound trucks under a fixed outbound truck schedule in multi-door cross docking operations

This paper studies the simultaneous dock assignment and sequencing of inbound trucks for a multi-door cross docking operation with the objective to minimize total weighted tardiness, under a fixed outbound truck departure schedule. The problem is newly formulated and solved by six different metaheuristic algorithms, which include simulated annealing, tabu search, ant colony optimization, differential evolution, and two hybrid differential-evolution algorithms. To evaluate the total weighted tardiness associated with any given inbound-truck sequence and dock assignment, an operational policy is developed. This policy is employed by every metaheuristic algorithm in searching for the optimal dock assignment and sequence. Each metaheuristic algorithm is tested with 40 problems. The major conclusions are: (1) metaheuristic is generally an effective optimization method for the subject problem; (2) population based metaheuristic algorithms are generally more effective than projection based metaheuristic algorithms; (3) proper selection of algorithmic parameters is important and more critical for projection based metaheuristic algorithms than population based algorithms; (4) the two best algorithms are ant colony optimization and hybrid differential evolution 2; among them, ACO takes less time than hybrid 2 and thus can be declared the best among all the six metaheuristic algorithms tested.     

Permutation flowshop scheduling to minimize the total tardiness with learning effects

Scheduling with learning effects has received considerable attention recently. Often, numbers of operations have to be done on every job in many manufacturing and assembly facilities. However, it is seldom discussed in the general multiple-machine setting, especially without the assumptions of identical processing time on all the machines or dominant machines. With the current emphasis of customer service and meeting the promised delivery dates, we consider a permutation flowshop scheduling problem with learning effects where the objective is to minimize the total tardiness. A branch-and-bound algorithm and two heuristic algorithms are established to search for the optimal and near-optimal solutions. Computational experiments are also given to evaluate the performance of the algorithms.     

Tabu search for minimizing total tardiness in a job shop

This paper presents a tabu search approach to minimize total tardiness for the job shop scheduling problem. The method uses dispatching rules to obtain an initial solution and searches for new solutions in a neighborhood based on the critical paths of the jobs. Diversification and intensification strategies are suggested. For small problems the solutions’ quality is evaluated against optimal solution values and for large problems the tabu search performance is compared with two heuristics proposed in the literature.     

Two-stage flowshop earliness and tardiness machine scheduling involving a common due window

This paper studies a non-preemptive two-stage flowshop scheduling problem to minimize the earliness and tardiness under the environment of a common due window. The window size and the window location are considered to be given parameters. The just-in-time problem exists naturally and has many practical applications. The problem is shown to be NP-complete in the strong sense. We develop a branch and bound algorithm and a heuristic to solve the problem. We conduct the computational experiments to test the performances of the algorithms. A strong lower bound is derived for the branch and bound algorithm that can efficiently solve 15 jobs problem for about 5 minutes. The heuristic is shown to be efficient and effective, which can solve the problem of 150 jobs for about 20 seconds and provide near-optimal solution. We justify that the heuristic is an excellent solution approach for large problem instances. We also show that four special cases are either polynomial solvable or NP-complete in the ordinary sense.     

Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity

Due-window assignment and production scheduling are important issues in operations management. In this study we investigate the problem of common due-window assignment and scheduling of deteriorating jobs and a maintenance activity simultaneously on a single-machine. We assume that the maintenance duration depends on its starting time. We provide polynomial time solutions for the problem and some of its special cases, where the objective is to simultaneously minimize the earliness, tardiness, due-window starting time, and due-window size costs.     

Metaheuristics for drilling operation scheduling in Taiwan PCB industries

Among all types of production environment, identical parallel machines are frequently used to increase the manufacturing capacity of the drilling operation in Taiwan printed circuit board (PCB) industries. Additionally, multiple but conflicting objectives are usually considered when a manager plans the production scheduling. Compared to the single objective problem, the multiple-objective version no longer looks for an individual optimal solution, but a Pareto front consisting of a set of non-dominated solutions will be needed and established. The manager then can select one of the alternatives from the set. This research aims at employing a variable neighborhood search (VNS) algorithm and a multiple ant colony optimization (MACO) algorithm to solve the identical parallel-machine scheduling problem with two conflicting objectives: makespan and total tardiness. In VNS, two neighborhoods are defined—insert a job to a different position or swap two jobs in the sequence. To save the computational expense, one of the neighborhoods is randomly selected for the target solution which is also arbitrarily chosen from the current Pareto front. In MACO, a two-phase construction procedure where three colonies are employed in each phase is proposed. These two algorithms are tested on a set of real data collected from a leading PCB factory in Taiwan and their performances are compared. The computational results show that VNS outperforms all competing algorithms—SPGA, MOGA, NSGA-II, SPEA-II, and MACO in terms of solution quality and computational time.     

A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search

The job-shop scheduling problem is one of the most arduous combinatorial optimization problems. Flexible job-shop problem is an extension of the job-shop problem that allows an operation to be processed by any machine from a given set along different routes. This paper present a new approach based on a hybridization of the particle swarm and local search algorithm to solve the multi-objective flexible job-shop scheduling problem. The particle swarm optimization is a highly efficient and a new evolutionary computation technique inspired by birds’ flight and communication behaviors. The multi-objective particle swarm algorithm is applied to the flexible job-shop scheduling problem based on priority. Also the presented approach will be evaluated for their efficiency against the results reported for similar algorithms (weighted summation of objectives and Pareto approaches). The results indicate that the proposed algorithm satisfactorily captures the multi-objective flexible job-shop problem and competes well with similar approaches.     

A hybrid artificial bee colony algorithm for the job shop scheduling problem

The job shop scheduling problem (JSSP) has attracted much attention in the field of both information sciences and operations research. In terms of the objective function, most existing research has been focused on the makespan criterion (i.e., minimizing the overall completion time). However, for contemporary manufacturing firms, the due date related performance is usually more important because it is crucial for maintaining a high service reputation. Therefore, in this study we aim at minimizing the total weighted tardiness in JSSP. Considering the high complexity, a novel artificial bee colony (ABC) algorithm is proposed for solving the problem. A neighborhood property of the problem is discovered, and then a tree search algorithm is devised to enhance the exploitation capability of ABC. According to extensive computational tests, the proposed approach is efficient in solving the job shop scheduling problem with total weighted tardiness criterion.     

Appointment scheduling of outpatient surgical services in a multistage operating room department

This article addresses the appointment scheduling of outpatient surgeries in a multistage operating room (OR) department with stochastic service times serving multiple patient types. We discuss many challenges, such as the limited availability of multiple resources (e.g., staff, operating rooms, surgeons, and recovery beds), and the compatibility of patient and surgeon types. In addition, availability of surgeons is restricted by time window constraints. Three simulation-based optimization methods have been proposed to minimize the patients’ wait time, patients’ completion time, and number of surgery cancellations. The first method is simulation-based tabu search (STS). It combines discrete-event simulation and tabu search to schedule surgery cases. The second and third methods are integer programming enhanced tabu search (IPETS) and binary programming enhanced tabu search (BPETS). IPETS and BPETS improve on STS by incorporating integer programming and binary programming models, respectively. This article includes a case study of an OR department in a major Canadian hospital. We further expand the actual data obtained in the case study to cover a wide range of parameters in sets of test problems, and provide analysis on the efficiency and effectiveness of the proposed methods in comparison with several scheduling rules. Finally, comments on the applications of the proposed methods are provided.     

Multi-agent-based transport planning in the newspaper industry

In many cases of today's planning tasks, the synchronization of production and distribution is becoming increasingly important in order to minimize costs and to maximize customer satisfaction. This is especially the case if transport schedules are closely connected to production schedules, as it is in the newspaper industry—where perishable goods are distributed immediately after production. In order to achieve the above mentioned competing objectives, a special kind of vehicle routing problem, the vehicle routing problem with time windows and cluster-dependent tour starts (VRPTWCD), has to be solved. Moreover, the varying print and post-processing schedules due to unknown editorial deadlines lead to the need for a dynamic online control of the newspaper production and distribution process. In this contribution, the outlined dynamic transport problem is solved online under consideration of unforeseen changes in production schedules. The solution concept is based on a multi-agent system consisting of, amongst others, several Edition and Vehicle Agents. This system is exemplarily applied to a real life application case of one of the largest German newspaper companies. It is shown that a static (centralized) optimization of the underlying problem would even lead to worse results in comparison to the current situation and that the appliance of the multi-agent system is suitable in the newspaper industry.     

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.     

Constraint programming for project-driven manufacturing

Project-driven manufacturing, based on the make-to-order or the build-to-order principle and predominant in small and medium-size enterprises (SMEs), calls for an efficient solution of large combinatorial problems, especially in such areas as task scheduling or resource management. This paper addresses the problem of finding a computationally effective approach to scheduling a new project subject to constraints imposed by a multi-project environment. A constraint programming (CP) modeling framework is discussed in the context of an efficient decomposition of the constraint satisfaction problem (CSP) and the evaluation of strategies for pruning the search tree. The proposed approach is illustrated through examples of its application to the evaluation of a new production order.     

基于遗传禁忌算法的任务分配与调度的研究

任务分配与调度问题是公认的NP问题,为了合理的对备份任务进行分配与调度,使得最短时间内完成备份任务, 提出了基于遗传禁忌搜索的备份任务调度算法。 重点研究了遗传算法和禁忌搜索算法,并针对二者的不足,提出将其两种算法混合,相互取长补短,仿真实验结果和实例应用表明,笔者提出的算法其搜索效率比单一的遗传算法具有较好的效果。     

The relationship between supply chain factors and adoption of e-Collaboration tools: An empirical examination

We consider minimum-cost scheduling of different vehicle types on a predetermined set of one-way trips. Trips have predetermined ready times, deadlines and associated demands. All trips must be performed. The total time of operations on any vehicle is limited. We develop a mixed integer model to find the optimal number of vehicles at a minimum cost. Based on the hard nature of the problem, we propose six heuristics. Computational results reveal that heuristics return exceptionally good solutions for problem instances with up to 100 jobs in very small computation times, and are likely to perform well for larger instances.     

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.     

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.     

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.     

Flexible job shop scheduling with due window—a two-pheromone ant colony approach

Recently, the companies reduce the manufacturing costs and increase capacity efficiency in the competitive environment. Therefore, to balance workstation loading, the hybrid production system is necessary, so that, the flexible job shop system is the most common production system, and there are parallel machines in each workstation. In this study, the due window and the sequential dependent setup time of jobs are considered. To satisfy the customers’ requirement, and reduce the cost of the storage costs at the same time, the sum of the earliness and tardiness costs is the objective. In this study, to improve the traditional ant colony system, we developed the two pheromone ant colony optimization (2PH-ACO) to approach the flexible job shop scheduling problem. Computational results indicate that 2PH-ACO performs better than ACO in terms of sum of earliness and tardiness time.     

Logistics scheduling to minimize inventory and transport costs

We study a logistics scheduling problem where a manufacturer receives raw materials from a supplier, manufactures products in a factory, and delivers the finished products to a customer. The supplier, factory and customer are located at three different sites. The objective is to minimize the sum of work-in-process inventory cost and transport cost, which includes both supply and delivery costs. For the special case of the problem where all the jobs have identical processing times, we show that the inventory cost function can be unified into a common expression for various batching schemes. Based on this characteristic and other optimal properties, we develop an O(n) algorithm to solve this case. For the general problem, we examine several special cases, identify their optimal properties, and develop polynomial-time algorithms to solve them optimally.     

Variable neighborhood search heuristic for nonconvex portfolio optimization

Abstract

In this article we consider a portfolio optimization problem under multiple real-world constraints, such as: cardinality constraints, tracking error, active share, and turnover. We propose a heuristic based on variable neighborhood search (VNS) that effectively addresses additional constraints that introduce non-convexities. In the VNS-based heuristic, several neighborhood structures are introduced and fast local search is implemented. We develop a VNS portfolio rebalancing framework (VNS-PRF) with two rebalance strategies. Data sets provided by a financial investment firm are used to evaluate the validity and reliability of the proposed VNS-PRF. Computational experiments and different portfolio performance measures indicate that our approach is able to obtain solutions with competitive quality and can be applied on large-scale data sets.