A novel dynamic genetic algorithm-based method for vehicle scheduling in cross docking systems with frequent unloading operation

An important factor for efficiently managing the supply chain is to efficiently control the physical flow of the supply chain. For this purpose, many companies try to use efficient methods to increase customer satisfaction and reduce costs. Cross docking is a good method to reduce the warehouse space requirements, inventory management costs, and turnaround times for customer orders. This paper proposes a novel dynamic genetic algorithm-based method for scheduling vehicles in cross docking systems such that the total operation time is minimized. In this paper, it is assumed that a temporary storage is placed at the shipping dock and inbound vehicles are allowed to repeatedly enter and leave the dock to unload their products. In the proposed method of this paper two different kinds of chromosome for inbound and outbound trucks are proposed. In addition, some algorithms are proposed including initialization, operational time calculation, crossover and mutation for inbound and outbound trucks, independently. Moreover a dynamic approach is proposed for performing crossover and mutation operation in genetic algorithm. In order to evaluate the performance of the proposed algorithm of this paper, various examples are provided and analyzed. The computational results reveal that the proposed algorithm of this paper performs better than two well-known works of literature in providing solutions with shorter operation time.     

A branch-and-bound algorithm for single-machine scheduling with batch delivery and job release times

This paper addresses scheduling a set of jobs with specified release times on a single machine for delivery in batches to customers or to other machines for further processing. This problem is a natural extension of minimizing the sum of flow times in the presence of release time by considering the possibility of delivering jobs in batches and introducing batch delivery costs. The scheduling objective adopted is that of minimizing the sum of flow times and delivery costs. The extended problem arises in the context of coordination between machine scheduling and a distribution system in a supply chain network. Structural properties of the problem are investigated and used to devise a branch-and-bound solution scheme. Computational experiments show significant improvement over an existing dynamic programming algorithm.     

A bi-level evolutionary optimization approach for integrated production and transportation scheduling

This paper investigates an integrated production and transportation scheduling (IPTS) problem which is formulated as a bi-level mixed integer nonlinear program. This problem considers distinct realistic features widely existing in make-to-order supply chains, namely unrelated parallel-machine production environment and product batch-based delivery. An evolution-strategy-based bi-level evolutionary optimization approach is developed to handle the IPTS problem by integrating a memetic algorithm and heuristic rules. The efficiency and effectiveness of the proposed approach is evaluated by numerical experiments based on industrial data and industrial-size problems. Experimental results demonstrate that the proposed approach can effectively solve the problem investigated.     

An improved approximation algorithm for single machine scheduling with job delivery

In single machine scheduling with release times and job delivery, jobs are processed on a single machine and then delivered by a capacitated vehicle to a single customer. Only one vehicle is employed to deliver these jobs. The vehicle can deliver at most c jobs in a shipment. The delivery completion time of a job is defined as the time in which the delivery batch containing the job is delivered to the customer and the vehicle returns to the machine. The objective is to minimize the makespan, i.e., the maximum delivery completion time of the jobs. We provide an approximation algorithm for this problem which is better than that given in the literature, improving the performance ratio from 5/3 to 3/2.     

Common due date assignment and scheduling with a rate-modifying activity to minimize the due date,earliness, tardiness,holding, and batch delivery cost

e consider a single-machine batch delivery scheduling and common due date assignment problem. In addition to making decisions on sequencing the jobs, determining the common due date, and scheduling job delivery, we consider the option of performing a rate-modifying activity on the machine. The processing time of a job scheduled after the rate-modifying activity decreases depending on a job-dependent factor. Finished jobs are delivered in batches. 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 a common due date for all the jobs, a location of the rate-modifying activity, and a delivery date for each job to minimize the sum of earliness, tardiness, holding, due date, and delivery cost. We provide some properties of the optimal schedule for the problem and present polynomial algorithms for some special cases.     

Job shop scheduling—A systematic approach

A systematic analysis of shop performance versus different scheduling rules is presented in this paper using a computer simulation model of a conventional job shop as a basis. The simulation model is used to identify dependent parameters such as shop load and service distribution for a set of scheduling rules. These conditions should represent different existing shop conditions. Six different scheduling rules and two different performance measures were used in the analysis. A complete statistical analysis and categorization of the simulation results were performed which produced some interesting anticipated as well as unanticipated results.     

A novel multi-objective meta-heuristic model for solving cross-docking scheduling problems

Cross-docking is a material handling and distribution technique in which products are transferred directly from the receiving dock to the shipping dock, reducing the need for a warehouse or distribution center. This process minimizes the storage and order-picking functions in a warehouse. In this paper, we consider cross-docking in a supply chain and propose a multi-objective mathematical model for minimizing the make-span, transportation cost and the number of truck trips in the supply chain. The proposed model allows a truck to travel from a supplier to the cross-dock facility and from the supplier directly to the customers. We propose two meta-heuristic algorithms, the non-dominated sorting genetic algorithm (NSGA-II) and the multi-objective particle swarm optimization (MOPSO), to solve the multi-objective mathematical model. We demonstrate the applicability of the proposed method and exhibit the efficacy of the procedure with a numerical example. The numerical results show the relative superiority of the NSGA-II method over the MOPSO method.     

Integrated process planning and scheduling in a supply chain

This paper deals with the integration of process planning and scheduling, which is one of the most important functions in a supply chain to achieve high quality products at lower cost, lower inventory, and high level of performance. Solving the problem is essential for the generation of flexible process sequences with resource selection and for the decision of the operation schedules that can minimize makespan. We formulate a mixed integer programming model to solve this problem of integration. This model considers alternative resources: sequences and precedence constraints. To solve the model, we develop a new evolutionary search approach based on a topological sort. We use the topological sort to generate a set of feasible sequences in the model within a reasonable computing time. Since precedence constraints between operations are handled by the topological sort, the developed evolutionary search approach produces only feasible solutions. The experimental results using various sizes of problems provide a way to demonstrate the efficiency of the developed evolutionary search approach.     

Locally perceiving hard global constraints in multi-agent scheduling

We propose how to model enterprise facilities (like factories, warehouses, etc.) in a multi-product production/distribution network, capacity management at those facilities, and scheduling agents which act as enterprise managers, taking decisions that affect the available capacity. A coordination mechanism through which scheduling agents can locally perceive hard global temporal constraints is also proposed.     

Manufacturing production plan optimization in three-stage supply chains under Bass model market effects

The Bass model is a very successful parametric approach to forecast the diffusion process of new products. In recent years, applications of the Bass model have been extended to other operational research fields such as managing customer demands, controlling inventory levels, optimizing advertisement strategies, and so forth. This study attempts to establish an application for optimizing manufacturers’ production plans in a three-stage supply chain under the Bass model’s effects on the market. The supply chain structure considered in this research is similar to other common supply chains comprised of three stages, namely retailer, distributor and manufacturer. The retailer stage has to handle customer demands following the Bass diffusion process. Market parameters and essential information are assumed to be available and ready for access. Each stage is expected to determine its inventory policy rationally. That is, each stage will attempt to maximize its own profits. These decisions will back-propagate their effects to upper stages. This study adopts a dynamic programming approach to determine the inventory policies of each stage so as to optimize manufacturers’ production plans.     

A note on “fuzzy multi-objective production/distribution planning decisions with multi-product and multi-time period in a supply chain”

Liang (2008) [Liang, T. -F. (2008). A note on “fuzzy multi-objective production/distribution planning decisions with multi-product and multi-time period in a supply chain”. Computers & Industrial Engineering, 55, 676–694] proposed a production/distribution planning model and its solution approach in fuzzy environment. However, his mathematical model does not use backordering option. The main purpose of this paper is to demonstrate this handicap and propose a valid constraint.     

Single-machine batch delivery scheduling with an assignable common due date and controllable processing times

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⁵) 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(nlog n) algorithm to solve it.     

Quantitative analysis of semiconductor supply chain contracts with order flexibility under demand uncertainty: A case study

The evidence base for the configuration of rolling horizon flexibility (RHF) contracts (a type of quantity flexibility contract) used in the semiconductor industry to coordinate production and demand remains meagre, more art than science. Informed by the characteristics of actual clauses and demand behaviors drawn from a company’s experience, a discrete-event simulation model is developed to represent the company’s supply chain. It comprises of three parties: a customer, a supplier (semiconductor manufacturer), and a capacity provider. Through analysis of customer forecasted demand the paper characterizes forecast demand as being under, over or unbiased. Models of these forecasted demands drives both long and short term planning. In long term planning, which is given twelve months before an order is delivered, capacity at the capacity provider is booked. Short term planning is also driven by this forecast which, within a binding period, is governed by an RHF contract. Results from the model report inventory levels, and delivery compliance, namely Delivery Performance (DP) and Delivery Reliability (DR), measures widely used in this sector. It is concluded from this work that on the balance of performance measures RHF contracts with asymmetrical flexibility bounds are substantially better than those with symmetrical boundaries, and that this conclusion is robust with regard to both over-planning and under-planning behaviors. This robustness is a critical attribute with respect to the endemic medium-term vacillation between both states experienced in practice in this sector.     

Project-driven planning and scheduling support for virtual manufacturing

The paper addresses the issue of decision-making support for small and medium-size enterprises operating within a virtual project-driven enterprise environment. The problem considered here can be defined in terms of finding a feasible schedule that satisfies the constraints imposed by the work-order duration, the price, and the time-constrained resource availability. The problem belongs to the class of multi-mode case problems of project scheduling, where finding a feasible solution is NP-hard. A heuristic method for process planning and scheduling is proposed. The method is based on a critical path approach and the branch and bound search scheme. It has been implemented in a web-enabled interactive software package, and is illustrated using the example of a virtual construction enterprise. Received: February 2005 / Accepted: January 2006     

An agent-based Decision Support System for resources' scheduling in Emergency Supply Chains

We propose a multi-agent-based architecture for the management of Emergency Supply Chains (ESCs), in which each zone is controlled by an agent. A Decision Support System (DSS) states and solves, in a distributed way, the scheduling problem for the delivery of resources from the ESC supplying zones to the ESC crisis-affected areas. Thanks to the agents’ cooperation, the DSS provides a scheduling plan that guarantees an effective response to emergencies. The approach is applied to two real cases: the Mali and the Japan crisis. Simulations are based on real data that have been validated by a team of logisticians from Airbus Defense and Space.     

Determination and exchange of supply information for co-operation in complex production networks

Today's manufacturing industry is characterised by strong interdependencies between companies operating in globally distributed production networks. The operation of such value-added chains has been enabled by recent developments in information and communication technologies (ICT) and computer networking. To gain competitive advantages and efficiency improvements such as reduced inventory and higher delivery reliability, companies are introducing information exchange systems that communicate demand to suppliers and production progress information to customers in the network. This article proposes a system that supports co-operation in complex production networks by enabling companies to determine and exchange supply information with their customers. The requirements for such a system are analysed and it is embedded in a framework of supply chain management business processes. The system facilitates the determination and exchange of meaningful, reliable and up-to-date order status information from the supplier to the customer. Based on comparing the progress of an internal production order with a pre-defined milestone model for each product, the status of the customer order is determined and—in case of lateness—communicated to the customer together with an early warning. To demonstrate the developed supply information concepts and processes, the business process is implemented as a pilot system and evaluated by the user companies participating in the 5th Framework IST project Co-OPERATE.     

A multi-dimensional job scheduling

With the advent of new computing technologies, such as cloud computing and contemporary parallel processing systems, the building blocks of computing systems have become multi-dimensional. Traditional scheduling systems based on a single-resource optimization, like processors, fail to provide near optimal solutions. The efficient use of new computing systems depends on the efficient use of several resource dimensions. Thus, the scheduling systems have to fully use all resources. In this paper, we address the problem of multi-resource scheduling via multi-capacity bin-packing. We propose the application of multi-capacity-aware resource scheduling at host selection layer and queuing mechanism layer of a scheduling system. The experimental results demonstrate performance improvements of scheduling in terms of waittime and slowdown metrics.     

Single-machine batch delivery scheduling with job release dates,due windows and earliness,tardiness, holding and delivery costs

This paper deals with a single-machine scheduling problem in which jobs are released in different points in time but delivered to customers in batches. A due window is associated with each job. The objective is to schedule the jobs, to form them into batches and to decide the delivery date of each batch so as to minimize the sum of earliness, tardiness, holding, and delivery costs. A mathematical model of the problem is presented, and a set of dominance properties is established. To solve this NP-hard problem efficiently, a solution method is then proposed by incorporating the dominance properties with an imperialist competitive algorithm. Unforced idleness and forming discontinuous batches are allowed in the proposed algorithm. Moreover, the delivery date of a batch may be decided to be later than the completion time of the last job in the batch. Finally, computational experiments are conducted to evaluate the proposed model and solution procedure, and results are discussed.     

Decomposition heuristic to minimize total cost in a multi-level supply chain network

In this paper, the distribution planning model for the multi-level supply chain network is studied. Products which are manufactured at factory are delivered to customers through warehouses and distribution centers for the given customer demands. The objective function of suggested model is to minimize logistic costs such as replenishment cost, inventory holding cost and transportation cost. A mixed integer programming formulation and heuristics for practical use are suggested. Heuristics are composed of two steps: decomposition and post improving process. In the decomposition heuristics, the problems are solved optimally only considering the transportation route first by the minimum cost flow problem, and the replenishment plan is generated by applying the cost-saving heuristic which was originally suggested in the manufacturing assembly line operation, and integrating with the transportation plan. Another heuristic, in which the original model is segmented due to the time periods, and run on a rolling horizon based method, is suggested. With the post-improving process using tabu search method, the performances are evaluated, and it was shown that solutions can be computed within a reasonable computation time by the gap of about 10% in average from the lower bound of the optimal solutions.     

A beam search heuristics to solve the parcel hub scheduling problem

In this paper, a beam search scheduling heuristic (BSSH) is presented to solve the parcel hub scheduling problem (PHSP), which is a scheduling problem that is common in the parcel delivery industry (PDI). Companies in the PDI include the United States Postal Service, United Parcel Services, Federal Express, and Deutsche Post. Together, these companies move more than one trillion dollars of the United States’ Gross Domestic Product. The PHSP involves scheduling a set of inbound trailers each containing a set of heterogeneous parcels to a set of unload docks. At the unload docks, the parcels are unloaded, sorted, and moved to the appropriate outbound trailers at the load docks. At the load docks, the parcels are loaded onto the outbound trailers. The objective is to minimize the timespan of the transfer operation at the transshipment terminal. The BSSH is compared to various scheduling approaches: random scheduling algorithm (RSA), genetic-based scheduling algorithm (GBSA), and simulation-based scheduling algorithm (SBSA). While GBSA and SBSA offer solutions that are superior to BSSH for smaller size problems, BSSH outperforms these algorithms on larger size problems requiring much less computational time. The results show that for larger size problems the BSSH is able to produce solutions that are from 4% to 8% of the known optimum solutions. In contrast, GBSA and SBSA, respectively offer solutions from 23% to 38% and from 6% to 47% of the known optimum solutions. The contribution of this paper is a scheduling heuristic to solve the PHSP.