The production-distribution problem with order acceptance and package delivery: models and algorithm
Department of Industrial Engineering, Islamic Azad University of Karaj, Moazen Blvd, Shoora Street, Karaj, Iran
2 Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Enghelab Street, South Moffateh Street, Tehran, Iran
* e-mail: firstname.lastname@example.org
Accepted: 8 October 2016
The production planning and distribution are among the most important decisions in the supply chain. Classically, in this problem, it is assumed that all orders have to produced and separately delivered; while, in practice, an order may be rejected if the cost that it brings to the supply chain exceeds its revenue. Moreover, orders can be delivered in a batch to reduce the related costs. This paper considers the production planning and distribution problem with order acceptance and package delivery to maximize the profit. At first, a new mathematical model based on mixed integer linear programming is developed. Using commercial optimization software, the model can optimally solve small or even medium sized instances. For large instances, a solution method, based on imperialist competitive algorithms, is also proposed. Using numerical experiments, the proposed model and algorithm are evaluated.
Key words: The production planning and distribution problem / Order acceptance / Scheduling / The package delivery / Imperialist competitive algorithm
© M. Khalili et al., Published by EDP Sciences, 2016
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Generally, the production planning is done in the short-term, mid-term and long-term of the three horizons of the time. The scheduling contains: the decision making in related to the production planning in the short-term time horizon which allocates the production capacity to the production targets. Its output is the exact determination of this issue that in which time and on what machine it should be process.
Deciding about the good’s delivery to the customers that it is a process in the short-term time horizon, – along with the supply and the production issues – is of the important decisions of every production complex. The package delivery is one of the delivery approaches. The delivery process is always done next to the production process. On the other hand, in the cases of we are required to respecting the delivery time determined by the customer, we obligate to coordinating the production program with the delivery requirements. As a result, the production and the delivery decisions are totally related to each other, so it is better that these two issues would be checked as integrated and simultaneous. In considering of the scheduling’s issue in the production and the package delivery approach to the delivery subject, the integrated issue will be contain the scheduling simultaneous determination and the package delivery. In the short-term time horizon, the available capacity of the production system is limited and usually is less than the necessary capacity for processing of all of the orders received by the system. So, a correct decision-making for the production planning, in addition to the scheduling determination and the works’ implementation sequence, includes the choice of the best orders from the orders’ basket received by the system. The approach of the orders’ choice from the received orders’ basket, is named so-called the order’s acceptance. The main idea of this study is presenting of an integrated issue in order to the simultaneous determination of the accepted orders for producing, the production sequence determination and the orders delivery to the customers with the package delivery approach.
A production system which works with the production strategy based on the order, in a planning period with having the short-term time horizon of (T), receives several orders (i) from several customers. These orders (Oij) have the processing time of (Pi), revenue (Ri) and the production cost (PCi). It assumes that the available time is not enough for all of the received orders. So, in attention to the time’s limitation, the producer likes accept the sales revenue and the production system’s costs of the best orders and plains for their processing and then delivery the orders to the customers. Delivering the orders to the customers that should be happen, in maximum, until the end of the period, is done simultaneously with the package delivery approach.
Each package can only contain the orders belong to one customer. The producer, after the processing completion of each order, will have three possibilities: at first, to send the order for the customer, immediately. In this case, we will have a package containing an order. Second, to send the processed order to the storehouse for processing the other orders that belong to the customer of the same order and then all of them would be sent in the form of one package. Third, the order which was processed, recently along with the orders that have already processed (and those belong to one customer) would be sent in form of a package. In this case, the order that has been processed recently, do not go to the storehouse, longer. If an order would be sent to the storehouse after processing, its handling cost (HCi) should be paid. This handling cost would be assumed depend on the order accumulation time. Totally, four categories of the cost are detected in this production system: the production’s cost, the preparation cost depend on the sequence, the handling cost and the cost of delivering the package which is depend on the number of the sent packages and independent of the number of the orders of inside the package. The objective function is the issue of maximizing the profit.
This profit achieves from the subtraction of the sales revenue and the costs.
The first research into the issue of scheduling and acceptance of the order was performed by Aslatnyk and Morton (1996) and Qsht (1997). In the study of Aslatnyk and Morton the manufacturing environment is single-machine and all orders are present at the zero time in the production system . Lewis and Slotnick investigated the multi-period scheduling and acceptance of the order. In this research, the planning horizon is divided into a number of courses . Moghaddam et al. recruited eight algorithms to solve the problem of single-machine scheduling and order rejection of that three algorithms are based on developing the simulated annealing method and five of them are according to the non-dominated sorting genetic algorithm (NSGA) one . Mokhtari developed a meta-intelligent Algorithm of water droplets for solving his bi-objective problem in the environment of parallel machines . Wang et al. investigated the problem of timing and acceptance of the order with the possibility of outsourcing in a few modes. The objective function is equal to accepted order minus the cost of outsourcing . Lu et al. presented the accurate polynomial time algorithm for optimal solution of scheduling problem and of rejecting the order in a single machine mode . Zhong and colleagues looked over the scheduling problem and order rejection in single-machine mode assuming the absence of a machine in some period of time . Moghaddam and colleagues examined the timing and order rejection in the form of a bi-objective optimization problem . He and his colleagues studied the order and timing in the environment of parallel machines. This order is defined for the “m” number of parallel machine and the “n” number of orders . Mokhtari studied the issue of minimizing the number of delayed orders (accepted orders) and fine rejects (for orders rejected) in the environment of parallel machines .
Khalili and Moghadam examined a scheduling problem in a “flow shop” environment that the objective function is the issues of minimizing “makespan” and “Total Weighted Tardiness”. In this issue all work may not be processing by all the available machines. Hereupon, they used the simulated annealing algorithm to solve the problem . Khalili examined a scheduling issue in a “hybrid no-wait flowshop” environment that the objective function is the issue of minimizing “makespan” and “Total Tardiness” . The timing issue and package delivery was determined first in 1993 by Kalbachr and Chang. He is the analysis of a single machine with the objective function minimizing total weighted earliness and delivery costs were closed . The main subject of their analysis was the issue of single machine problem with the objective function of minimizing the total weighted earliness and also the package delivery cost . Wang and Cheng also examined the issue of timing and package delivery on parallel machines in 2000 . Mahdavi Mazdeh and colleagues applied the objective function of minimizing the total current time work and delivery costs for scheduling tasks in the single machine mode . Ji et al. showed that scheduling problem and package delivery on the single machine and with the objective function of minimizing the total cost of current work load and delivery costs is a NP-hard strongly problem . Mahdavi Mazdeh and colleagues investigated the issue of scheduling and package delivery on the single machine with the assumption that works are not necessarily available at the zero time and each work consists the time of arrival to the workshop . Mahdavi Mazdeh and his colleagues studied the single-machine scheduling and package delivery with the objective function of total weighted current work time order and package delivery cost . Hamidinia Hamidinia and colleagues proposed a non-linear model using genetic algorithms to solve the problem of single-machine scheduling and package delivery . Selvarajah and Zhang developed an innovative solution for scheduling and package delivery problem with the objective function of total weighted current work time order and package delivery cost .
In a short period of time T, the manufacturer intends to submit orders among incoming orders that considering time constraints, system costs, and earnings per order, the most profits would be gained.
The manufacturing environment is single-machine and it is continuously available during the planning period.
At any time, only one order is processed.
Interruption of work (work breakdown) is not allowed.
Before any order processing, preparation is necessary that its duration is dependent on the sequence.
The manufacturer is obliged to deliver customer orders up to the end of the period.
Delivering the package is performed according to the package delivery approach.
Packages have no capacity constraints.
The costs of the system are: the cost of production (processing), maintenance costs and preparation costs (considered to be a multiple of preparation time), delivery costs (depending on the number of packages).
The objective function is to maximize the benefits derived from the difference between sales revenue minus the cost of the entire system.
In this study, design of simultaneously scheduling model, the acceptance of orders and deliveries, considering the capacity constraints, sequence-dependent setup and package delivery approaches are discussed. This model is based on the Mixed Integer Linear Programming (MILP). For describing the above model, the index, parameters and variables used are shown in Table 1.
Parameters and variables of decision.
The equation (1) shows the objective function maximize profit. The profit is obtained from the difference between sales revenue minus the cost (maintenance, preparation, production and delivery). The equation (2) shows that if i order is accepted, the order shall be terminated before the end of the (T) time horizon and if the i order is not accepted the completion time order does not mean and is considered as zero. The equation (3) shows that if i order is accepted, the complete time order of i equal to start time plus processing time and if i order is not be accepted, start time is equal to end time. The equation (4) shows that if the i′ order to be processed after the order i, the i′ start order at least is equal to the time of completion the task i plus the i′ preparation time work, and if the i′ order is not processing after i order, the restrictions will be thwarted. The equation (5) suggests that the number of times that the preparation is done, is equal to the number of orders accepted, except to the first work in which the preparatory work is not done. The equation (6) shows if i order to be accepted, certainly is considered somewhere in the production sequence and if not, there is no place in the production sequence for it. The equation (7) shows if i order to be accepted, certainly is considered somewhere in the production sequence and if not, there is no place in the production sequence for it. The equation (8) shows that if i order to be accepted it must be assigned to a batch like k and if i order is not accepted it has no place in any of the batches delivered. The equation (9) indicates that each batch such as k can only include customer orders like costumer j. The equations (10) and (11) requiring the model that only if k batch belongs to the customer j, the customer orders like i belong to customer j can be allocated to k batch and contrary, if the customer orders like i belong to customer j be placed in k batch then k batch will be allocated to customer j. The equation (12) indicates the completion of k batch, is at least equal to the time of completion of the last job within the batch (if k batch includes i order). The equation (13) shows that the delivery time of i, is at least equal to the completion of the k batch (if k batch includes i order). The equation (14) represents the total number of batches delivered to the customer j. The equation (15) shows the variable types.
Due to the linearity of the mathematical model, by using the Gomez software, the optimal solution can be obtained. Considering that for the large size it is very time-consuming that problem to be solved, in this way solving time is limited to 3600 s. According to the state to solve every problem with precision, the issues are divided into three categories: small issues (problems to optimally be solved by exact method in 3600 s), medium (problems that are unlikely to be solved in 3600 s by exact method, but at least a feasible solution is found for them) and large (problems that no feasible solution cannot be found for them over 3600 s).
Imperialist is the policy of extending the power and rule of a government beyond its own boundaries. A country may attempt to dominate others by direct rule or less obvious means such as a control of markets for goods or raw materials. The latter is often called Neocolonialism. In its initial forms imperialism was just a political control over other countries in order to only use their sources. Also in some cases the reason to control another country was just preventing the opponent imperialist from taking possession of it. No matter what the reason was the imperialist states were competing strongly for increasing their colonies and spreading their empires over the world. This competition resulted in a development of powerful empires and the collapse of weaker ones .
Flowchart of the proposed algorithm.
The goal of optimization is to find an optimal solution in terms of the variables of the problem. We form an array of variable values to be optimized. This array is called “country”. In an Nvar dimensional optimization problem a country is a 1 × Nvar array. This array is defined by(16)
To start the optimization the algorithm we generate the initial population of size Npop. We select Nimp of the most powerful countries to form the empires. The remaining of Ncol of the population will be the colonies each of which belongs to an empire. Then we have to types of countries: imperialist and colony. To form the initial empires, we divided the colonies among imperialists based on their power. That is the initial number of colonies of an empires should be directly proportionate to its power. To divide the colonies among imperialists proportionally, we define the normalized cost of an imperialist by(18)where cn is the cost of nth imperialist Cn is its normalized cost. Having the normalized cost of all imperialists, the normalized power of each imperialist is defined by(19)
From another point of view, the normalized power an imperialist is the portion of colonies that should be possessed by that imperialist. Then the initial number of colonies of an empire will be(20)where N.C.n is the initial number of colonies of nth empire and Ncol is the number of all colonies. To divide the colonies, for each imperialist we randomly choose N.C.n of the colonies and give them to it. Figure 2 shows how initial empires are Generating.
Generating initial empires.
Imperialist countries started to improve their colonies. We have modeled this fact by moving all the colonies toward the imperialist. This movement is shown in Figure 3, in which the colony moves toward the imperialist by x units. The new position of colony is shown in a darker color. The direction of the moment is the vector from colony to imperialist. In this figure x is a random variable with uniform distribution. Then for x we have(21)where β is a number greater than 1 and d is the distance between colony and imperialist. A β > 1 causes the colonies to get closer to the imperialist state from both sides.
Moving colonies toward their relevant imperialists.
To search different points around the imperialist we add a random amount of deviation to the direction of movement. Figure 4 shows the new direction. In this figure θ is a random number of with uniform (or any proper) distribution. Then(22)where γ is a parameter that adjust the deviation from the original direction. Nevertheless the values of β and γ are arbitrary, in most of our implementation a value of about 2 for β and about π/4 for γ have resulted in good convergence of counties to the global minimum.
Moving colonies toward their relevant imperialists in a randomly deviated direction.
While moving toward the imperialist, a colony may reach to a position with lower cost than that of imperialist. In such a case the imperialist moves to the position of that colony and vice versa. Then algorithm will continue by the imperialist in a new position and then colonies start moving toward this position. Figure 5 shows how a colony exchange the positions of the imperialist.
Exchanging positions of the imperialist and a colon.
Total power of an empire is mainly effected by the power of imperialist country. But the power of the colonies of an empire has an effect on the total power of that empire. We have modeled this fact by defining the total cost by(23)where T.N.C.n is the total cost of the nth empire and ξ is a positive number which is considered to be less than 1. A little value for ξ causes the total power of the empire to be determined by just the imperialist and increase the rule of the colonies in determining the total power of an empire. We have used the value of 0.1 for ξ in most of our implementation.
All empires try to take possession of colonies of other empires and control them. This imperialistic competition gradually brings about a decrease in the power of weaker empires and an increase in the power of more powerful ones. We model this competition by just picking some (usually one) of the weakest colonies of the weakest empires and making a competition among all empires to possess these (this) colonies. To start the competition, first, we find the possession probability of each empire based on its total power. The normalized total cost is simply obtained by(24)where T.C.n and N.T.C.n are respectively total cost and normalized total cost of nth empire. Having the normalized total cost, the possession probability of each empire is given by(25)
Referring to vector D, we will hand the mentioned colonies to an empire whose relevant index in D is maximum.
Powerless empires will collapse in the imperialistic competition and their colonies will be divided among other empires. In modeling collapse mechanism different criteria can be defined for considering an empire powerless. In most of our implementation, we assume an empire collapsed and eliminated it when it loses all of its colonies. Figure 6 shows how a powerless empires is eliminated.
Eliminating the powerless empires.
After a while all the empires except the most powerful one will collapse and all the colonies will be under the control of this unique empire. In this ideal new world all the colonies will have the same positions and same costs and they will be controlled by an imperialist with the same position and cost as themselves. In this ideal world, there is no difference not only among colonies but also between colonies and imperialist. In such a condition we put an end to the imperialistic competition and stop the algorithm. In the next part we apply the proposed algorithm to some of benchmark problems in the optimization. The main steps in the algorithm are summarized in the pseudo-code shown in Figure 7.
Pseudo-code for the proposed algorithm.
Demand, costs and revenue of each order.
Set up times for orders.
(T = 20) & (SC = 5 ST).
To solve the problem, at first we should accept the orders based on indices T, Pi, ST:
Sequencing of orders.
Sequencing of orders.
Now, suppose orders are delivered by these batches:
Order 1 to customer 1.
Orders 4 & 5 to customer 2.
Order 3 to customer 3.
|(Ri − PCi)||80||60||50||50||240|
|SCi||2 × 5||10|
|DCj||(2 × 25) + (1 × 20)||70|
|(deli − ci)HCi||1.5 × 3.5||5.25|
Z = 240 − 10 − 70 − 5.25 = 154.75.
The 23 randomly generated samples are distinct based on two parameters: the number of orders (i) and customer number (j).
In this method, the mathematical model is designed to determine the order at the reception, scheduling and delivery of a package with the aim of finding the optimal solution in a Gomez software environment. Considering that solving problem for large size is very time consuming, in this way it is limited to 3600 s. Table 3 shows the results of a detailed method of problem solving.
Meta heuristic correct functioning depends on set parameters. Therefore, before using this colonial competition method first it is necessary to set the parameter
First, for iteration parameter a value of 100 and for β coefficient value of 0.8 is considered, then for each parameter number of value is selected based on trial and error method. Table 2 shows the values of various parameters. Based on Table 4 a total of 12 different combinations for algorithm parameters that a compound should be selected among them. To choose the best combination of parameters, the number of five issues of the optimal sample issues are available using the independent component analysis (ICA) algorithm, with 12 different parameter combinations been solved and the solution obtained been compared with the optimal solution. Any combination of parameters which provides closest solution to the optimal solutions in solving these five problems is selected. ICA algorithm similarity with the optimal solution is measured using relative deviation Total Relative Gap (TRG) indicators.
Comparison between different combinations of parameters of ICA method.
TRGq values for 12 combinations of parameter shown in Table 4, the lowest amount is for the compound (5). Hereupon, this algorithm parameter values is chosen according to below: nPop = 20, nEmp = 7, kesi = 1/5.
Based on the observations, for small size problems, the optimal solution using the exact method is achieved in less time than one hour. Table 5 provides a comparison between the answers obtained from two solutions and shows the relative deviation from the optimal solution for ICA method. The relative deviation according to equation (31) is obtained.
Comparison of the results obtained from two methods for solving the problems of small size.
In this equation opt is optimum value according to these exact method and sol is observed value based on the ICA method.
Since the optimal solution is not available in medium and large size problems, the comparison of observed results are discussed. Table 6 shows the objective function for two solution method. In the ICA method, the best objective function value observed for each sample is given.
Comparison of two solution methods for solving problems of medium-sized and large-sized samples.
The relative deviation of the objective function value according to equation (32) calculated and presented.
In this equation, the ICA best is the function objective value according to the ICA method and sol is the objective function value obtained according the exact method.
For the problems of small size, the optimal solution is obtained using the exact method in limited time to 3600 s. The best response in all matters of ICA method is equal to the optimal solution. Therefore, for the small size problems, we recommend using both exact solution and ICA. In medium and large size problems with the enlargement of the scale of the problem, gradually ICA method is to produce better solutions than the exact method.
The reason for this is that, in line with the enlargement of the problem scale and the exponential increase in time required for the optimal solution, the solution technique which is limited to 3600 s, compared to the time required for the optimal solution would be negligible and this fact improve the quality of the results with the ICA method.
In literature, two criteria are common: (1) delivery after production and (2) delivery at the end of period.
But, batch delivery, according to the definition, is a more comprehensive approach compared to the previous approach. In batch delivery maybe a product to be sent for a customer with a batch. This is equivalent with delivery after production. By the way, it maybe all goods to be sent for a customer with a package. This is equivalent with delivery at the end of period. Despite comprehensive batch delivery, to verify this way than two others, a comparison between three methods is done.
Comparison between benefits of three methods in numerical example.
The approach used in comparison between three methods in numerical example is applied for small size problems. Table 8 is shown results of three methods.
Comparison between benefits of three methods in small size problems.
According to the results, batch delivery, always maximize benefit of a production system.
- J.B. Ghosh, Job selection in a heavily loaded shop, Computers & Operations Research 24 (1997) 141–145. [CrossRef] (In the text)
- H. Lewis, S. Slotnick, Multi-period job selection: planning workloads to maximize profit, Computers & Operations Research 29 (2002) 1081–1098. [CrossRef] (In the text)
- A. Moghaddam, F. Yalaoui, L. Amodeo, Efficient meta-heuristics based on various dominance criteria for a single-machine bi-criteria scheduling problem with rejection, Journal of Manufacturing Systems 34 (2015) 12–22. [CrossRef] (In the text)
- H. Mokhtari, A nature inspired intelligent water drops evolutionary algorithm for parallel processor scheduling with rejection, Applied Soft Computing 26 (2015) 166–179. [CrossRef] (In the text)
- X. Wang, Q. Zhu, T. Cheng, Subcontracting price schemes for order acceptance and scheduling, Omega 54 (2015) 1–10, DOI: 10.1016/j.omega.2015.01.005. [CrossRef] (In the text)
- L. Lu, C. Ng, L. Zhang, Optimal algorithms for single-machine scheduling with rejection to minimize the makespan, International Journal of Production Economics 130 (2011) 153–158. [CrossRef] (In the text)
- X. Zhong, J. Ou, G. Wang, Order acceptance and scheduling with machine availability constraints, European Journal of Operational Research 232 (2014) 435–441. [MathSciNet] (In the text)
- J. Ou, X. Zhong, G. Wang, An improved heuristic for parallel machine scheduling with rejection, European Journal of Operational Research 241 (2015) 653–661. [MathSciNet] (In the text)
- M. Khalili, R. Moghaddam, A multi-objective electromagnetism algorithm for a bi-objective flowshop scheduling problem, Journal of Manufacturing Systems 31 (2012) 232–239. [CrossRef] (In the text)
- M. Khalili, A multi-objective electromagnetism algorithm for a bi-objective hybrid no-wait flowshop scheduling problem, The International Journal of Advanced Manufacturing Technology 70 (2014) 1591–1601. [CrossRef] (In the text)
- M. Mahdavi Mazdeh, A.N. Esfahani, S. Sakkaki, A.E. Pilerood, Single machine batch scheduling minimizing weighted flow times and delivery costs with job release times, International Journal of Industrial Engineering Computations 3 (2012) 347–364. [CrossRef] (In the text)
- G. Wang, T. Cheng, Parallel machine scheduling with batch delivery costs, International Journal of Production Economics 68 (2000) 177–183. [CrossRef] (In the text)
- M. Mahdavi Mazdeh, M. Sarhadi, K. Hindi, A branch-and-bound algorithm for single-machine scheduling with batch delivery minimizing flow times and delivery costs, European Journal of Operational Research 183 (2007) 74–86. [CrossRef] (In the text)
- M. Ji, Y. He, T. Cheng, Batch delivery scheduling with batch delivery cost on a single machine, European Journal of Operational Research 176 (2007) 745–755. [MathSciNet] (In the text)
- M. Mahdavi Mazdeh, M. Sarhadi, K. Hindi, A branch-and-bound algorithm for single-machine scheduling with batch delivery and job release times, Comput. Oper. Res. 35 (2008) 1099–1111. [MathSciNet] (In the text)
- M. Mahdavi Mazdeh, S. Shashaani, A. Ashouri, K. Hindi, Single-machine batch scheduling minimizing weighted flow times and delivery costs, Applied Mathematical Modelling 35 (2011) 563–570. [MathSciNet] (In the text)
- A. Hamidinia, S. Khakabimamaghani, M. Mahdavi Mazdeh, M. Jafari, A genetic algorithm for minimizing total tardiness/earliness of weighted jobs in a batched delivery system, Computers & Industrial Engineering 62 (2012) 29–38. [CrossRef] (In the text)
- E. Selvarajah, R. Zhang, Supply chain scheduling at the manufacturer to minimize inventory holding and delivery costs, International Journal of Production Economics 147A (2014) 117–124. [CrossRef] (In the text)
- E. Atashpaz-Gargari, C. Lucas, Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition, IEEE Congress on Evolutionary Computation (CEC 2007) (2007) 4661–4667. [CrossRef] (In the text)
Cite this article as: Khalili M, Esmailpour M & Naderi B: The production-distribution problem with order acceptance and package delivery: models and algorithm. Manufacturing Rev. 2016, 3, 18.
Moving colonies toward their relevant imperialists in a randomly deviated direction.
|In the text|