Integrated order acceptance and scheduling decision making in product service supply chain with hard time windows constraints

Bin Dan; Huali Gao; Yang Zhang; Ru Liu; Songxuan Ma

doi:10.3934/jimo.2017041

Article Contents

2018, Volume 14, Issue 1: 165-182. Doi: 10.3934/jimo.2017041

This issue Previous Article Joint decision on pricing and waste emission level in industrial symbiosis chain Next Article Optimal control of switched systems with multiple time-delays and a cost on changing control

Integrated order acceptance and scheduling decision making in product service supply chain with hard time windows constraints

a.
School of Economics and Business Administration, Chongqing University, Chongqing 400044, China
b.
Research Center of Business Administration & Economic Development, Chongqing University, Chongqing 400030, China
c.
School of Management, Southwest University of Political Science & Law, Chongqing 401120, China

* Corresponding author: danbin@cqu.edu.cn (B Dan)
* Corresponding author: danbin@cqu.edu.cn (B Dan)

Received: December 31, 2014

Revised: November 30, 2016

Early access: March 2017

Published: January 2018

This research was supported by the National Natural Science Foundation of China (Grant Number: 71272086), the National Science and Technology supporting Program of China (Grant Number: 2015BAF05B01), and the Specialized Research Fund for the Doctoral Program of Higher Education of China (20120191110042).

Abstract Full Text(HTML) Figure(1) / Table(5) Related Papers Cited by

Abstract

A product service supply chain (PSSC) supplies customers with product-service systems (PSS) consist of integrated products and services. The product manufacturing should match the service supply in the order delivery planning. For PSS orders are usually delivered under time window constraints, this paper is concerned with the integrated order acceptance and scheduling (OAS) decision of the PSSC. Defined the PSS orders by their revenues, product processing times, serving offering times and hard time window constraints, we formulate the OAS problem as a MILP model to optimize total revenue of PSSC and propose two effective value for big-M to solve the problem with small size optimally. The simulated annealing algorithm based on the priority rule of servable orders first (SOF-SA) and the dynamic acceptance and scheduling heuristic (DASH) algorithm are presented. The performance of the model and the two algorithms are proved through simulating instances with different order sizes. Computational tests show that the SOF-SA algorithm is more effective when used for small size problems while the DASH algorithm is more effective for problems with larger size; negotiating with customers to make reasonable delivery time windows should be beneficial to increasing total revenue and improving the decision efficiency.

Keywords:

Mathematics Subject Classification: Primary: 49K30, 49K35; Secondary: 90C11.

Citation:

Full Text(HTML)

Figure 1. Graphical representation of the OAS problem in PSSC

Download: Full-size image PowerPoint slide

Table 1. The performance of MA

$\tau $	$R$	$M=\sum_{i=1, ..., n} {(t_{pi} +t_{si} )} $ CPU(s)		$\widehat{M_{ij} }=d_{li} +t_{sj} $ CPU(s)
$\tau $	$R$	$n\text{=}10$	$n\text{=}12$	$n\text{=}10$	$n\text{=}12$
0.1	0.2	19.45	684.96	19.55	675.23
0.1	0.4	1.28	104.66	1.19	103.99
0.1	0.6	0.36	24.52	0.34	24.75
0.2	0.2	2.45	149.15	2.30	126.21
0.2	0.4	0.41	11.61	0.39	11.5
0.2	0.6	0.13	0.07	0.28	0.07
0.3	0.2	1.20	4.57	1.19	4.08
0.3	0.4	1.97	0.16	1.91	0.23
0.3	0.6	0.06	0.54	0.06	0.54

| Show Table

DownLoad: CSV

Table 2. The algorithms' performance for $n = 10$

$n$	$\tau $	$R$	GAP1(%)		CPU(s)
$n$	$\tau $	$R$	SOF-SA	DASH	SOF-SA	DASH
10	0.1	0.2	13.7	16.2	31.63	3.15
10	0.1	0.4	7.1	9.5	20.32	1.21
10	0.1	0.6	14.4	15.8	13.87	0.89
10	0.2	0.2	16.6	19.1	43.57	0.75
10	0.2	0.4	21.4	23.6	24.33	0.67
10	0.2	0.6	15.5	22.7	15.21	0.62
10	0.3	0.2	18.2	19.1	50.92	0.56
10	0.3	0.4	7.2	15.8	28.69	0.53
10	0.3	0.6	20.6	23.4	24.36	0.27

| Show Table

DownLoad: CSV

Table 3. The algorithms' performance for $n = 20$

$n$}	$\tau $	$R$	GAP2(%)		CPU(s)
$n$}	$\tau $	$R$	SOF-SA	DASH	SOF-SA	DASH
20	0.1	0.2	5.8	11.0	97.04	3.76
20	0.1	0.4	11.7	19.1	45.73	1.61
20	0.1	0.6	9.2	14.4	39.97	1.45
20	0.2	0.2	11.9	12.3	120.38	1.32
20	0.2	0.4	5.0	8.8	52.67	1.19
20	0.2	0.6	9.4	12.1	46.89	0.96
20	0.3	0.2	7.4	13.0	168.42	0.88
20	0.3	0.4	12.2	15.6	38.54	0.73
20	0.3	0.6	9.1	13.5	37.45	0.65

| Show Table

DownLoad: CSV

Table 4. The algorithms' performance for $n = 50$

$n$	$\tau $	$R$	GAP2(%)		CPU(s)
$n$	$\tau $	$R$	SOF-SA	DASH	SOF-SA	DASH
50	0.1	0.2	9.5	15.8	735.14	10.68
50	0.1	0.4	17.0	20.4	530.87	5.49
50	0.1	0.6	20.9	21.3	521.22	5.31
50	0.2	0.2	12.6	15.0	822.36	5.16
50	0.2	0.4	16.2	17.7	579.54	4.88
50	0.2	0.6	17.1	19.0	566.97	4.79
50	0.3	0.2	18.4	22.6	899.53	4.45
50	0.3	0.4	22.7	26.5	620.28	4.15
50	0.3	0.6	15.3	15.8	619.99	3.65

| Show Table

DownLoad: CSV

Table 5. The algorithms' performance for $n = 100$

$n$	$\tau $	$R$	GAP2(%)		CPU(s)
$n$	$\tau $	$R$	SOF-SA	DASH	SOF-SA	DASH
100	0.1	0.2	25.8	19.2	1365.49	32.54
100	0.1	0.4	30.3	17.7	954.21	25.57
100	0.1	0.6	19.7	10.4	996.73	24.66
100	0.2	0.2	25.1	18.8	1681.32	23.09
100	0.2	0.4	27.9	26.1	1307.76	21.85
100	0.2	0.6	29.4	27.0	1178.54	21.73
100	0.3	0.2	32.0	19.9	1873.55	20.42
100	0.3	0.4	26.5	21.2	1054.27	19.81
100	0.3	0.6	35.2	25.5	1175.92	17.65

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	T. S. Baines, H. W. Lightfoot, S. Evans, ... and J. R. Alcock, State-of-the-art in product-service systems, Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 221 (2007), 1543-1552. doi: 10.1243/09544054JEM858.
[2]	F. H. Beuren, M. G. G. Ferreira and P. A. C. Miguel, Product-service systems: a literature review on integrated products and services, Journal of Cleaner Production, 47 (2013), 222-231. doi: 10.1016/j.jclepro.2012.12.028.
[3]	B. Cesaret, C. Oǧuz and F. S. Salman, A tabu search algorithm for order acceptance and scheduling, Computers & Operations Research, 39 (2012), 1197-1205. doi: 10.1016/j.cor.2010.09.018.
[4]	H. K. Chen, C. F. Hsueh and M. S. Chang, Production scheduling and vehicle routing with time windows for perishable food products, Computers & Operations Research, 36 (2009), 2311-2319. doi: 10.1016/j.cor.2008.09.010.
[5]	R. Esmaeilbeigi, P. Charkhgard and H. Charkhgard, Order acceptance and scheduling problems in two-machine flow shops: New mixed integer programming formulations, European Journal of Operational Research, 251 (2016), 419-431. doi: 10.1016/j.ejor.2015.11.036.
[6]	M. Garetti, P. Rosa and S. Terzi, Life Cycle Simulation for the design of Product-Service Systems, Computers in Industry, 63 (2012), 361-369. doi: 10.1016/j.compind.2012.02.007.
[7]	T. C. Kuo, Simulation of purchase or rental decision-making based on product service system, The International Journal of Advanced Manufacturing Technology, 52 (2011), 1239-1249. doi: 10.1007/s00170-010-2768-2.
[8]	T. C. Kuo and W. M. Ling, The optimisation of maintenance service levels to support the product service system, International Journal of Production Research, 50 (2012), 6691-6708. doi: 10.1080/00207543.2011.616916.
[9]	I. S. Lee, Minimizing total tardiness for the order scheduling problem, International Journal of Production Economics, 144 (2013), 128-134. doi: 10.1016/j.ijpe.2013.01.025.
[10]	S. Lee, Y. Geum, H. Lee and Y. Park, Dynamic and multidimensional measurement of product-service system (PSS) sustainability: a triple bottom line (TBL)-based system dynamics approach, Journal of Cleaner Production, 32 (2012), 173-182. doi: 10.1016/j.jclepro.2012.03.032.
[11]	N. Li and Z. Jiang, Modeling and optimization of a product-service system with additional service capacity and impatient customers, Computers & Operations Research, 40 (2013), 1923-1937. doi: 10.1016/j.cor.2013.02.015.
[12]	Y. K. Lin and C. S. Chong, A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem, Journal of Industrial and Management Optimization, 12 (2016), 703-717. doi: 10.3934/jimo.2016.12.703.
[13]	H. Lockett, M. Johnson, S. Evans and M. Bastl, Product Service Systems and supply network relationships: An exploratory case study, Journal of Manufacturing Technology Management, 22 (2011), 293-313. doi: 10.1108/17410381111112684.
[14]	C. Low, R. Li and C. Chang, Integrated scheduling of production and delivery with time windows, International Journal of Production Research, 51 (2012), 897-909. doi: 10.1080/00207543.2012.677071.
[15]	E. Manzini and C. Vezzoli, A strategic design approach to develop sustainable product service systems: Examples taken from the 'environmentally friendly innovation' Italian prize, Journal of Cleaner Production, 11 (2003), 851-857. doi: 10.1016/S0959-6526(02)00153-1.
[16]	R. Maull, A. Smart and L. Liang, A process model of product service supply chains, Production Planning & Control, 25 (2014), 1091-1106. doi: 10.1080/09537287.2013.808840.
[17]	O. K. Mont, Clarifying the concept of product-service system, Journal of Cleaner Production, 10 (2002), 237-245. doi: 10.1016/S0959-6526(01)00039-7.
[18]	F. T. Nobibon and R. Leus, Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment, Computers & Operations Research, 38 (2011), 367-378. doi: 10.1016/j.cor.2010.06.003.
[19]	C. Oguz, F. S. Salman and Z. B. Yalçin, Order acceptance and scheduling decisions in make-to-order systems, International Journal of Production Economics, 125 (2010), 200-211.
[20]	T. Sakao, A. Ö. Rönnbäck and G. Ö. Sandström, Uncovering benefits and risks of integrated product service offerings—Using a case of technology encapsulation, Journal of Systems Science and Systems Engineering, 22 (2013), 421-439. doi: 10.1007/s11518-013-5233-6.
[21]	L. H. Su, P. S. Chen and S. Y. Chen, Scheduling on parallel machines to minimise maximum lateness for the customer order problem, International Journal of Systems Science, 44 (2013), 926-936. doi: 10.1080/00207721.2011.649366.
[22]	C. A. Ullrich, Integrated machine scheduling and vehicle routing with time windows, European Journal of Operational Research, 227 (2013), 152-165. doi: 10.1016/j.ejor.2012.11.049.
[23]	UNEP, The role of product service systems in a sustainable society, In. http://www.unep.fr/scp/design/pdf/pss-brochure-final.pdf, (2001).
[24]	X. Wang, X. Xie and T. C. E. Cheng, Order acceptance and scheduling in a two-machine flowshop, International Journal of Production Economics, 141 (2013), 366-376. doi: 10.1016/j.ijpe.2012.08.020.
[25]	X. Wang, X. Xie and T. C. E. Cheng, A modified artificial bee conoly algorithm for order acceptance in two-machine flowshop, International Journal of Production Economics, 141 (2013), 14-23.
[26]	Y. Xiao, R. Zhang, Q. Zhao and I. Kaku, Permutation flow shop scheduling with order acceptance and weighted tardiness, Applied Mathematics and Computation, 218 (2012), 7911-7926. doi: 10.1016/j.amc.2012.01.073.
[27]	W. Xie, Z. Jiang, Y. Zhao and X. Shao, Contract design for cooperative product service system with information asymmetry, International Journal of Production Research, 52 (2014), 1658-1680. doi: 10.1080/00207543.2013.847293.
[28]	Z. Xu, X. Ming, W. Song, M. ~Li, L. He and X. Li, Towards a new framework: Understanding and managing the supply chain for product-service systems, Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 0954405414521189, (2014). doi: 10.1177/0954405414521189.
[29]	L. Zhang, L. Lu and J. Yuan, Single machine scheduling with release dates and rejection, European Journal of Operational Research, 198 (2009), 975-978. doi: 10.1016/j.ejor.2008.10.006.
[30]	C. Zhao, Y. Yin, T. C. E. Cheng and C. C. Wu, Single-machine scheduling and due date assignment with rejection and position-dependent processing times, Journal of Industrial and Management Optimization, 10 (2014), 691-700. doi: 10.3934/jimo.2014.10.691.
[31]	X. Zhong, J. Ou and G. Wang, Order acceptance and scheduling with machine availability constraints, European Journal of Operational Research, 232 (2014), 435-441. doi: 10.1016/j.ejor.2013.07.032.